题意

参考思路

代码

主要是记录一下自己的写的代码，中间debug好久，在一些小地方犯错

#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<ctime>#include<vector>#include<map>#include<algorithm>#include<set>#include<string>#include<queue>#include<stack>using namespace std;#define ll long long#define fi first#define se second#define sc(n) scanf(\"%d\",&n)#define exp 1e-9typedef pair<ll, ll> lp;typedef pair<int,int> ii;typedef vector<vector<ll> > vvl;const int inf = 0x3f3f3f3f;const ll mod = 1e9 + 7;const double PI = acos(-1);int lowbit(int x){return x&(-x);}void update(vector<int>& data,int x,int delta){while(x<data.size()){data[x]+=delta;x+=lowbit(x);}}int query(vector<int>& data,int x){int ans=0;while(x){ans+=data[x];x-=lowbit(x);}return ans;}void J(){int t;sc(t);for(int kase=1;kase<=t;kase++){//cout<<\"debug1\"<<endl;int n;sc(n);vector<ii> a;vector<int> data(n+1,0);//1 表示空位的数量vector<int> res(n+1,0);//data[0]=0;//build(data);for(int i=1;i<=n;i++){int x,y;scanf(\"%d %d\",&x,&y);a.emplace_back(x,y);update(data,i,1);}sort(a.begin(),a.end());bool error=false;for(int i=1;i<=n;i++){//按身高从小到大安放每个人的位置//二分每个人的最佳位置if(a[i-1].second>n-i) {error=true;break;}int l=1,r=n;int p=min(a[i-1].second,n-i-a[i-1].second)+1;while(l<r){//cout<<l<<\" \"<<r<<endl;int mid=l+(r-l)/2;//二分每个位置，找到那个pos，使得前pos位恰好有p个空位int cnt=query(data,mid);if(cnt<p) l=mid+1;else r=mid;}update(data,l,-1);//更新空位，在该位置res[l]=a[i-1].first;}if(error){printf(\"Case #%d: impossible\\n\",kase);}else{printf(\"Case #%d:\",kase);for(int i=1;i<=n;i++) printf(\" %d\",res[i]);printf(\"\\n\");}}}int main() {//    freopen(\"C:\\\\data\\\\code\\\\cppCode\\\\kuangbin_bi_slide_monoQueue\\\\in.txt\", \"r\", stdin);//    freopen(\"C:\\\\data\\\\code\\\\cppCode\\\\kuangbin_bi_slide_monoQueue\\\\out.txt\", \"w\", stdout);//    ios::sync_with_stdio(false);//    cin.tie(0);//    cout.tie(0);J();}