题目链接:http://poj.org/problem?id=2182
题意:给定1~n个数和n个位置,已知ai表示第i个位置前有ai个数比当前位置的数小,求这个排列。
和刚才YY的题意蛮接近的,用树状数组维护当前数组内数字分别是第几大的,倒着查询,每次查尽可能靠右的位置,可以保证取的数字是未取到并且不会冲突。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cstdlib> 5 using namespace std; 6 7 #define lowbit(x) x & (-x) 8 const int maxn = 8080; 9 int n; 10 int a[maxn]; 11 int bit[maxn]; 12 13 void update(int i, int x) { 14 while(i <= n) { 15 bit[i] += x; 16 i += lowbit(i); 17 } 18 } 19 20 int sum(int i) { 21 int ret = 0; 22 while(i) { 23 ret += bit[i]; 24 i -= lowbit(i); 25 } 26 return ret; 27 } 28 29 int ub(int val) { 30 int lo = 1, hi = n; 31 while(lo <= hi) { 32 int mid = (lo + hi) >> 1; 33 if(sum(mid) >= val) hi = mid - 1; 34 else lo = mid + 1; 35 } 36 return lo; 37 } 38 39 void dfs(int i) { 40 if(i == 0) return; 41 int pos = ub(a[i]+1); 42 update(pos, -1); 43 dfs(i-1); 44 printf("%d ", pos); 45 } 46 47 int main() { 48 //freopen("in", "r", stdin); 49 while(~scanf("%d", &n)) { 50 memset(a, 0, sizeof(a)); 51 memset(bit, 0, sizeof(bit)); 52 for(int i = 1; i <= n; i++) update(i, 1); 53 for(int i = 2; i <= n; i++) scanf("%d", &a[i]); 54 dfs(n); 55 } 56 return 0; 57 }