谜一样的牛
-
在这一题中,最后一头牛前面有 $k$ 头比它高的牛就说明它是高度 $k+1$ 的牛。比如最后一头牛前面有2头比它高的牛,则说明其是第3高的牛。
-
这道题可以从后往前遍历,把每一个身高如果被选中了设置为0,未被选中设置为1,这样我们可以通过求编号所对应的 前缀和 来确定这个编号前面还有几头比其还高的牛。而这个前缀和数组可以使用 树状数组 来优化为 $0(logn)$ 的时间复杂度,这样可以避免 $O(n^2)$ 时间复杂度导致超时的问题。
-
在查找当前身高为 $k$ 的牛的身高应该为多少的时候可以用二分结合树状数组来做。
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1E5 + 10;
int tr[N], a[N], ans[N];
int n;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin >> n;
for (int i = 2; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) add(i, 1);
for (int i = n; i; i -- )
{
int k = a[i] + 1;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (k <= sum(mid)) r = mid;
else l = mid + 1;
}
ans[i] = l;
add(l, -1);
}
for (int i = 1; i <= n; i ++ ) cout << ans[i] << endl;
return 0;
}