谜一样的牛 树状数组+二分

本文主要是介绍谜一样的牛 树状数组+二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

谜一样的牛

有 $n$ 头奶牛，已知它们的身高为 $1\sim n$ 且各不相同，但不知道每头奶牛的具体身高。

现在这 $n$ 头奶牛站成一列，已知第 $i$ 头牛前面有 $A_i$ 头牛比它低，求每头奶牛的身高。

输入格式

第 $1$ 行：输入整数 $n$。

第 $2..n$ 行：每行输入一个整数 $A_i$，第 $i$ 行表示第 $i$ 头牛前面有 $A_i$ 头牛比它低。
（注意：因为第 $1$ 头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含 $n$ 行，每行输出一个整数表示牛的身高。

第 $i$ 行输出第 $i$ 头牛的身高。

数据范围

$1\le n\le 10^5$

输入样例：

5
1
2
1
0

输出样例：

2
4
5
3
1

构造一个$sum(i)=i$的树状数组,则$sum(1)=1,sum\ast (2)=2...sum(n)=n$,逆序遍历$A[]$数组,因为$A[n]$的后面没有牛,那么先给$A[n]$找到位置(二分查找),假设为$po{s}_n$,那么树状数组中$po{s}_i$后面的所有数全部减去$1$( $update(po{s}_i,-1)$ ),因为$po{s}_i$这个位置的牛是在最后面,不是在$po{s}_i\sim n$的牛的前面,不属于前面的牛,所有之后的都要减去$1$.

树状数组维护$A[]$,使用二分查找每头牛的位置.

树状数组求前缀和时间复杂度为$O(logn)$

二分查找时间复杂度$O(logn)$

时间复杂度为$O(nlo{g}^{2}n)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5+5;
int n; 
int A[maxn],res[maxn];
int C[maxn];
void update(int i,int v)
{while(i<=n) {C[i] += v;i += (i & -i);}
}
int sum(int i)
{int res = 0;while(i > 0) {res += C[i];i -= (i & -i);}return res;
}
int main()
{scanf("%d",&n);for(int i=2;i<=n;++i)scanf("%d",&A[i]);for(int i=1;i<=n;++i) C[i] = i & -i;for(int i=n;i>=1;--i){int v = A[i] + 1;int l = 1 , r = n;while(l < r){int mid = l + r >> 1;if(sum(mid) >= v) r = mid;else l = mid + 1;}res[i] = l;update(l,-1);}for(int i=1;i<=n;++i){printf("%d\n",res[i]);}return 0;
}

这篇关于谜一样的牛 树状数组+二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---