Bubble Sort
Time Limit: 2000ms
Memory Limit: 262144KB
This problem will be judged on CodeForcesGym. Original ID: 100517B64-bit integer IO format: %I64d Java class name: (Any)
解题：我们发现假设当前位选择1,那么发现比1大的并且没有使用的有b个，那么当前为选1，后面就还有$2^{b-1}$种方式，所以贪心的选，只要使得后面的方案数大于当前的k即可，如果少于了怎么办？比如当前是1，然后把当前的值改为2，k减去当前位选1的时候的方案数，类似搞，直到后面的方案的数不少于k
代码写的确实烂了点
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 100010; 5 int c[maxn]; 6 void add(int i,int val) { 7 while(i < maxn) { 8 c[i] += val; 9 i += i&-i; 10 } 11 } 12 int sum(int i,int ret = 0) { 13 while(i > 0) { 14 ret += c[i]; 15 i -= i&-i; 16 } 17 return ret; 18 } 19 bool used[maxn]; 20 int n,ans[maxn]; 21 LL k; 22 LL check(int x) { 23 if(x < 0) return 0; 24 LL ret = 1; 25 for(int i = 0; i < x; ++i){ 26 if(ret >= k) return ret; 27 ret <<= 1; 28 } 29 return ret; 30 } 31 int main() { 32 #define NAME "bubble" 33 freopen(NAME".in","r",stdin); 34 freopen(NAME".out","w",stdout); 35 while(scanf("%d%I64d",&n,&k),n||k) { 36 memset(used,false,sizeof used); 37 memset(c,0,sizeof c); 38 for(int i = 1; i <= n; ++i) add(i,1); 39 int cur = 1; 40 for(int i = 1; i < n; ++i) { 41 while(used[cur]) ++cur; 42 int big = sum(n) - sum(cur); 43 if(check(big-1) >= k) { 44 ans[i] = cur; 45 used[cur] = true; 46 add(cur,-1); 47 } else { 48 int t = cur + 1; 49 k -= check(big-1); 50 while(used[t]) ++t; 51 int xx = sum(n) - sum(t); 52 while(xx && check(xx-1) < k) { 53 k -= check(xx-1); 54 ++t; 55 while(used[t]) ++t; 56 xx = sum(n) - sum(t); 57 } 58 used[t] = true; 59 ans[i] = t; 60 add(t,-1); 61 } 62 } 63 for(int i = 1; i <= n; ++i) 64 if(!used[i]) { 65 ans[n] = i; 66 break; 67 } 68 for(int i = 1; i <= n; ++i) 69 printf("%d%c",ans[i],i==n?' ':' '); 70 } 71 return 0; 72 } 73 /* 74 1 2 3 4 5 75 1 2 3 5 4 76 1 2 4 3 5 77 1 2 5 3 4 78 1 3 2 4 5 79 1 3 2 5 4 80 1 4 2 3 5 81 1 5 2 3 4 82 2 1 3 4 5 83 2 1 3 5 4 84 2 1 4 3 5 85 2 1 5 3 4 86 3 1 2 4 5 87 3 1 2 5 4 88 4 1 2 3 5 89 5 1 2 3 4 90 */