正題

題目鏈接:http://poj.org/problem?id=2182

---

題目大意

給出每頭牛前面有多少個(gè)比它高的，求每頭牛的最大高度。

---

解題思路

建立一個(gè)01序列，表示每個(gè)高度是否被占用過，然后倒序掃描每次找到一個(gè)沒有被占用的第Ai+1個(gè)位置，然后標(biāo)記占用。
我們可以用樹狀數(shù)組表示每個(gè)高度前面有多少個(gè)沒被占用，然后用二分找到答案。

---

code

#include<cstdio> #define lobit(x) x&-x using namespace std; 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]); }

總結(jié)

以上是生活随笔為你收集整理的POJ2182-Lost Cows【树状数组,二分】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。