题目大意:
已知有N个人,每个人的身高都不同,他们排成一列,而且他们记得他们的身前或者是身后有K个人比他高,问是否存在这样的可行序列,如果存在,输出最小字典序的解,否则输出impossible.
思路1:
①首先我们将序列按照身高从大到小排序,那么当前排列到第i个人的时候,已知所有之前排列上的人都比他高,所以只要将这个人插入到合适的位子即可,并且这个位子我们尽可能的靠向左边。
②当且仅当k>i-1的时候无解。
③那么过程用伸展树维护一下即可。
附上队长Ac代码:
#include <bits/stdc++.h> typedef long long int LL; typedef unsigned long long int LLu; using namespace std; const int N = 100000+5; const int MOD = 998244353; const int INF = 1e9+7; inline int read() { int x = 0,f=1; char ch = getchar(); for(; ch<'0'||'9'<ch; ch=getchar()) if(ch == '-') f=-1; for(; '0'<=ch&&ch<='9'; ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; return x*f; } #define lal puts("****"); #define pb push_back #define mp make_pair /********************************************************/ /*************SPLAY-tree************/ int n,m; int ch[N][2]; //ch[][0] lson ch[][1] rson int f[N]; //father int sz[N]; //size int val[N]; //value of node_i int cnt[N]; // counts of the node_i int root; //root of splay-tree int tot; //tot,total,is the number of node of tree void pushup(int x){ if(x)sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x]; } void rotate(int x,int k){ // k = 0 左旋, k = 1 右旋 int y=f[x];int z=f[y]; ch[y][!k]=ch[x][k];if(ch[x][k])f[ch[x][k]]=y; f[x]=z;if(z)ch[z][ch[z][1]==y]=x; f[y]=x;ch[x][k]=y; pushup(y),pushup(x); } void splay(int x,int goal){ for(int y=f[x];f[x]!=goal;y=f[x]) rotate(x,(ch[y][0]==x)); if(goal==0) root=x; } void newnode(int rt,int v,int fa){ // printf("newnode : rt = %d\n",rt); f[rt]=fa;val[rt]=v,sz[rt]=cnt[rt]=1; ch[rt][0]=ch[rt][1]=0; } void delnode(int &rt){ //其实是为内存回收做准备的 回头再完善 f[rt]=val[rt]=sz[rt]=cnt[rt]=0; ch[rt][0]=ch[rt][1]=rt=0; } /***************************以下是DEBUG***************************/ void Traversal(int rt){ if(!rt) return; Traversal(ch[rt][0]); printf("%d f[]=%d sz[]=%d lson=%d rson=%d val[]=%d\n",rt,f[rt],sz[rt],ch[rt][0],ch[rt][1],val[rt]); Traversal(ch[rt][1]); } void debug(){ printf("ROOT = %d <---\n",root); Traversal(root); } /**************************以下是前置操作**************************/ //以x为根的子树 的极值点 0 极小 1 极大 int extreme(int x,int k){ while(ch[x][k])x=ch[x][k];splay(x,0); return x; } //以x为根的子树 第k个数的位置 int kth(int x,int k){ if(sz[ch[x][0]]+1<=k&&k<=sz[ch[x][0]]+cnt[x]) return x; else if(sz[ch[x][0]]>=k) return kth(ch[x][0],k); else return kth(ch[x][1],k-sz[ch[x][0]]-cnt[x]); } int search(int rt,int x){ if(ch[rt][0]&&val[rt]>x) return search(ch[rt][0],x); else if(ch[rt][1]&&val[rt]<x)return search(ch[rt][1],x); else return rt; } /***************************以下是正经操作*************************/ //前驱 int prec(int x){ int k=search(root,x); splay(k,0);//debug(); if(val[k]<x) return k; return extreme(ch[k][0],1); } //后继 int sufc(int x){ int k=search(root,x); splay(k,0);//debug(); if(val[k]>x) return k; return extreme(ch[k][1],0); } int rk(int x){ int k=search(root,x); splay(k,0); return sz[ch[root][0]]+1; } //在第k个数后插入值为x的节点 void _insert(int k,int x){ int r=kth(root,k),rr=kth(root,k+1); splay(r,0),splay(rr,r); newnode(++tot,x,rr);ch[rr][0]=tot; for(r=rr;r;r=f[r])pushup(r); splay(rr,0); } /*****************************************************/ struct node { int h,k; }a[N]; bool cmp(node a,node b){ return a.h>b.h; } int ans[N]; void dfs(int rt){ if(!rt) return ; dfs(ch[rt][0]); ans[++ans[0]]=val[rt]; dfs(ch[rt][1]); } int main(){ int _ = 1,kcase = 0; for(scanf("%d",&_);_--;){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].k); sort(a+1,a+n+1,cmp); printf("Case #%d:",++kcase); bool flag = false; for(int i=1;i<=n;i++) if(a[i].k>=i) flag =true; if(flag ){ puts(" impossible"); continue; } tot=0,root=1; newnode(++tot,-INF,0),newnode(++tot,INF,root); ch[root][1]=tot; for(int i=1;i<=n;i++){ a[i].k=min(a[i].k,i-1-a[i].k); _insert(a[i].k+1,a[i].h); } ans[0]=0; dfs(root); for(int i=2;i<ans[0];i++) printf(" %d",ans[i]); puts(""); } return 0; } 思路2:
①我们将序列按照身高从小到大排序,那么当前假设到第i个人入列的时候,我们之前入队的所有人都比他矮,那么他在如队的时候,只要身前留下min(k,n-i-k)个位子即可。
②所以我们一开始的时候,将一颗树状数组都置1,表示所有位子都还没有被占用过,过来一个人的时候,二分树上剩余位子的第min(k+1,n-i-k+1)个位子即可,如果存在这个位子,那么将这个人放到这个位子上,否则结果就是impossible.
③过程用树状数组套二分去跑就行了。
Ac代码:
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; struct node { int h,k; }a[100005]; int tree[100005];//树 int ans[100005]; int n; int cmp(node a,node b) { return a.h<b.h; } int lowbit(int x)//lowbit { return x&(-x); } int sum(int x)//求和求的是比当前数小的数字之和,至于这里如何实现,很简单:int sum=sum(a[i]); { int sum=0; while(x>0) { sum+=tree[x]; x-=lowbit(x); } return sum; } void add(int x,int c)//加数据。 { while(x<=n) { tree[x]+=c; x+=lowbit(x); } } int main() { int t; int kase=0; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++)scanf("%d%d",&a[i].h,&a[i].k),add(i,1); sort(a+1,a+1+n,cmp); int flag=1; for(int i=1;i<=n;i++) { int pos=min(a[i].k+1,n-(i+a[i].k)+1); if(pos<1)flag=0; if(flag==0)break; int l=1; int r=n; int output=-1; while(r-l>=0) { int mid=(l+r)/2; if(sum(mid)<pos) { l=mid+1; } else { output=mid; r=mid-1; } } if(output==-1)flag=0; else ans[output]=a[i].h,add(output,-1); } printf("Case #%d: ",++kase); if(flag==0)printf("impossible\n"); else { for(int i=1;i<=n;i++) { if(i>1)printf(" "); printf("%d",ans[i]); } printf("\n"); } } }