思路
初始化所有数为1 代表没有用过
从后往前计算 找到还未用过的前k小的数是几 使得sum(x) == k成立的最小x即为答案
然后将这个数置为0 表示已经用过
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。
现在这n头奶牛站成一列，已知第i头牛前面有A i
头牛比它低，求每头奶牛的身高。
输入格式
第1行：输入整数n。
第2…n行：每行输入一个整数A i ,第i行表示第i头牛前面有A i
头牛比它低。（注意：因为第1头牛前面没有牛，所以并没有将它列出）
输出格式
输出包含n行，每行输出一个整数表示牛的身高。
第i行输出第i头牛的身高。
数据范围
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 100010; int tr[N], h[N], ans[N]; int n; void add(int x, int c) { for (int i = x; i <= n; i += lowbit(i))tr[i] += c; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i))res += tr[i]; return res; } int check(int x) { int l = 1, r = n; while (l < r) { int mid = l + r >> 1; if (query(mid) >= x)r = mid; else l = mid + 1; } add(r, -1); return r; } int main() { cin >> n; for (int i = 2; i <= n; ++i)scanf("%d", &h[i]); for (int i = 1; i <= n; ++i)tr[i] = lowbit(i); for (int i = n; i; --i) { int k = h[i] + 1; ans[i] = check(k); } for (int i = 1; i <= n; ++i)printf("%d\n", ans[i]); return 0; }
