题目链接

题目大意

每个奶牛都有一个编号，1- N 从第二个牛开始给出前面比她编号小的牛的个数，问你求牛的编号序列

思路分析

从后往前看，最后一头牛可以确定它的号码，因为知道了前面有k头比它小的，k+1即为它号码。记a[i]为第i头牛在它前面有多少头牛号码比它小的（即输入值），那么如何计算第k-1头牛的编号？

我们从1到N进行遍历，记录$a[k-1]$个没有访问过的编号（没有访问过即没有被他之后的牛$a[k]$所使用的编号），那么第$a[k]$个编号即该牛的编号，整个过程如下所示

#define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 8005 int N, vis[MAX], r[MAX], a[MAX]; int main() { while (scanf("%d", &N) != EOF) { a[0] = 0; for (int i = 1; i < N; i++)scanf("%d", &a[i]); memset(vis, 0, sizeof(vis)); memset(r, 0, sizeof(r)); for (int i = N - 1; i >= 0; i--) { int cnt = 0; for (int j = 1; j <= N; j++) { if (!vis[j]) { if (cnt == a[i]) { r[i] = j; vis[j] = 1; break; } cnt++; } } } for (int i = 0; i < N; i++) cout << r[i] << endl; } }

当然这样做的复杂度显然是$N^2$的，这道题勉强可过，但是数据一多就凉了，因此我们可以进行进一步的优化，我们可以用树状数组表示每个编号前面有多少个没被占用，然后用二分找到答案。

#define lobit(x) x&-x int c[8001],n,a[8001],ans[8001]; void add(int x,int num) { while(x<=n) { c[x]+=num; x+=lobit(x); } } int ask(int x) { int sum=0; while(x) { sum+=c[x]; x-=lobit(x); } return sum; } int low(int x)//二分答案 { int l=1,r=n; while(l<=r) { int mid=(l+r)/2; if(ask(mid)+x<=mid) r=mid-1; else l=mid+1; } return l; } int main() { scanf("%d",&n); a[1]=0; for(int i=2;i<=n;i++) scanf("%d",&a[i]); for(int i=n;i>=1;i--) { int w=low(a[i]+1);//找到位置 ans[i]=w;//记录答案 add(w,1);//占用该位置 } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); }