PKU 2182 Lost Cows
http://poj.org/problem?id=2182
n匹の牛が並んでいる。それぞれの牛には1〜nまでの番号が振ってあり、同じ番号は2度以上現れることはない。
ここで、n-1個の数字が入力される。i番目の数字は1〜i番目に並んでいる牛のうち、i+1番目の牛よりも小さい番号を持っている牛の数を表している。
牛の並び順を特定しろというような問題。
入力の後ろから見ていくと、順番に特定していくことができる。
O(n^2logn)程度でも何とか通るようです。
int in[8000],ans[8000]; main(){ int n; cin>>n; int in[n]; rep(i,n-1)cin>>in[i]; set<int> app; rep(i,n)app.insert(i+1); rep(i,n-1){ int t=in[n-i-2]; set<int>::iterator p=app.begin(); rep(j,t)++p; int k=*p; ans[n-i-1]=k; app.erase(k); } ans[0]=*app.begin(); rep(i,n)cout<<ans[i]<<endl; }