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

柔光的暖阳◎ 2023-01-10 15:54 148阅读 0赞

**题目描述**  
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。

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

**输入格式**  
第1行：输入整数n。

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

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

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

**数据范围**  
1≤n≤105

**输入样例：**

5
    1
    2
    1
    0

**输出样例：**

2
    4
    5
    3
    1

对于做数据结构的题目，数据结构本身不难，难的是我们怎么把他抽象成用数据结构操作。

题目数据给出每头牛前面有几头牛比它矮，对于样例来看

第1头牛前面没有牛、第2头牛前面有1头牛比他矮、第3头牛前面有2头牛比他矮、第4头牛前面有1头牛比他矮、第5头牛前面有0头牛比他矮。

数据 ：0 1 2 1 0  
我们正向不好看，倒着看。

最后一头牛，前面没有比他矮的，说明它是最矮的 。**1**、2、3、4、5，选择1作为身高。  
倒数第2头牛，前面有1头牛比他矮，说明它是剩余身高中第二矮的。2、**3**、4、5，选择3作为身高。  
倒数第3头牛，前面有2头牛比他矮，说明它是剩余身高中第三矮的。2、4、**5**，选择5作为身高。  
倒数第4头牛，前面有1头牛比他矮，说明它是剩余身高中第二矮的。2、**4**，选择4作为身高。  
倒数第5头牛，前面有0头牛比他矮，说明它是剩余身高中最矮的。**2**，选择2作为身高。

答案即 2、4、5、3、1

所以，我们根据分析的结论可以得出，对于第i头牛，他的身高=剩余身高中第k+1矮的（k是前面比他矮的牛）。

**逻辑操作**：  
倒序遍历每一头牛  
对于每一头牛

1.  在剩余的身高中找第k+1小的。
2.  删除找到的身高

如果用二重循环肯定会TLE。

查询剩余身高我们尽量希望是log级别的，因为我们要遍历所有牛不能优化，查询尽可能的更快。

所以查询我们要使用二分查找，二分查找需要在一个有序数组里，考虑到还有删除操作，我们想到了**树状数组**。

删除操作很简单。

分析查询：  
我们把树状数组的初始值附为1，代表这个身高还没用过。  
对于第i头牛，他前面有m头牛比他矮，二分查找sum（x）>=m+1，也就是找第一个>=m+1的下标，下标就是该牛的身高。  
sum函数是树状数组的前缀和。  
sum（1 ~ n）一定是一个单调递增的数，因为我们初始值为1，如果用过一个身高，则变成0，所以无论怎么变，sum（1 ~ n）一定是一个递增的数。

比如 ：  
剩余身高 ：有 1 2 3 4 5 （1、4被用过了）  
树状数组维护的数组 为 0 1 1 0 1  
sum函数维护的前缀和为：0 1 2 2 3  
如果我们找剩余身高中第2矮的，二分查询第一个sum（x）的下标>=2的，下标3就是该牛的身高。

整个时间复杂度O（N \* logN \* logN）  
Code：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    typedef long long ll;
    const ll N=1e5+10;
    using namespace std;
    ll h[N],a[N],tr[N],ans[N];
    ll n;
    ll lowbit(ll x)
    { 
    	return x&-x;
    }
    void add(ll pos,ll x)
    { 
    	for(int i=pos;i<=n;i+=lowbit(i))  tr[i]+=x;
    }
    ll sum(ll x)
    { 
    	ll res=0;
    	for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    	return res;
    }
    int main()
    { 
    	ios::sync_with_stdio(false);
    	cin>>n;
    	for(int i=2;i<=n;i++) cin>>h[i];
    	for(int i=1;i<=n;i++) add(i,1);	
    	for(int i=n;i;i--)
    	{ 
    		ll k=h[i]+1;
    		ll l=1,r=n;
    		while(l<r)
    		{ 
    			ll mid=l+r>>1;
    			if(sum(mid)>=k) r=mid;
    			else l=mid+1;
    		}
    		add(r,-1);
    		ans[i]=r;
    	}
    	for(int i=1;i<=n;i++)
    		cout<<ans[i]<<endl;
    	return 0;
     }