题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5592
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 483 Accepted Submission(s): 236
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int num[50005]; int ans[50005]; int aa[50005]; struct Tree { int x, sum; }a[200005]; void Build(int rt, int l, int r, int n) { if(l == r) { a[rt].x = l; a[rt].sum = 1; return ; } Build(rt*2, l, (l+r)/2, n); Build(rt*2+1, (l+r)/2+1, r, n); a[rt].sum = a[rt*2].sum + a[rt*2+1].sum; } int Querry(int rt, int l, int r, int num) { int ans; if(l == r) { a[rt].sum--; return a[rt].x; } if(num > a[rt*2].sum) ans = Querry(rt*2+1, (l+r)/2+1, r, num - a[rt*2].sum); else ans = Querry(rt*2, l, (l+r)/2, num); a[rt].sum--; return ans; } int main() { int t, n; scanf("%d", &t); while(t--) { scanf("%d", &n); aa[0] = 0; for(int i=1; i<=n; i++) { scanf("%d", &aa[i]); num[i] = aa[i] - aa[i-1];//num[i]保存i前面有多少个比ans[i]大 } Build(1, 1, n, n); for(int i=n; i>=1; i++) { ans[i] = Querry(1, 1, n, num[i]+1); } for(int i=1;i<=n;i++) { printf("%d%c",ans[i],i==n?‘\n‘:‘ ‘); } } return 0; }
HDU 5592 ZYB's Premutation(BestCoder Round #65 C)
原文:http://www.cnblogs.com/mengzhong/p/5026420.html