試題鏈接

題意：

求出一個１到ｎ的排列，這個排列只告訴了你從第二個數字開始的比這個數字小的數的個數。

題解：

如果一個數p，p的前面有m個比他小的數，后面有n個比他小的數，那p的位置就是n+m+1
我們可以二分這個p，如果m+n+1>mid,mid就取小了；否則就取大了
p前面有多少比他小的數，在輸入答案時就知道了
p后面有多少比他小的數，可以用樹狀數組來搞定
我們在處理時應該倒序處理，想想最后一個數的真實值就是a[n]+1,然后刪除最后一個數，看倒數第二個，一次類推即可

代碼：

# include<cstdio> # include<iostream> # include<fstream> # include<algorithm> # include<functional> # include<cstring> # include<string> # include<cstdlib> # include<iomanip> # include<numeric> # include<cctype> # include<cmath> # include<ctime> # include<queue> # include<stack> # include<list> # include<set> # include<map>using namespace std;const double PI=4.0*atan(1.0);typedef long long LL; typedef unsigned long long ULL;# define inf 999999999 # define MAX 8000+4int a[MAX]; int ans[MAX]; int tree[MAX];int n; int lowbit(int x) {return x&(-x); } int getsum ( int pos )//后面比他小的數字的個數 {int ans = 0;while ( pos > 0 ){ans+=tree[pos];pos-=lowbit(pos);}return ans; }void update ( int pos,int val ) {while ( pos <= n ){tree[pos]+=val;pos+=lowbit(pos);} }int my_search ( int k ) {int left = 1, right = n;while ( left < right ){int mid = ( left+right )>>1;int num = getsum (mid);if ( mid - 1 < num+k ){left = mid+1;}else{right = mid;}}return left; }int main(void) {while ( scanf("%d",&n)!=EOF ){memset(tree,0,sizeof(tree));memset(ans,0,sizeof(ans));a[1] = 0;for ( int i = 2;i <= n;i++ )scanf("%d",&a[i]);for ( int i = n;i >= 1;i-- ){int k = my_search(a[i]);update(k,1);//每確定一個位置，進行更新 ans[i] = k;}for ( int i = 1;i <= n;i++ )printf("%d\n",ans[i]);}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Lost Cows（树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。