#include<stdio.h> #include<queue> #include<string.h> #define Max 1000100 #define inf 0x3f3f3f3f using namespace std; int max(int x,int y){if(x>y) return x;return y;} int min(int x,int y){if(x>y) return y;return x;} int Hash[Max]; int n; int t[Max*4]; int a[Max]; inline void push_up(int p) { t[p]=min(t[p<<1],t[p<<1|1]); } void build(int o,int l,int r) //建立线段树 { if(l==r) { t[o]=l; return; } int mid=(l+r)>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); push_up(o); } void update(int o,int l,int r,int p) //把p位置变成inf { if(l==r){t[o]=inf;return;} else { int m=(l+r)>>1; if(p<=m) update(o<<1,l,m,p); else update(o<<1|1,m+1,r,p); push_up(o); } } int query(int o,int l,int r,int nowl,int nowr) //查询 { if(nowl<=l&&r<=nowr) return t[o]; int m=(l+r)>>1; int ans=inf; if(nowl<=m) ans=query(o<<1,l,m,nowl,nowr); if(nowr>m) ans =min(ans,query(o<<1|1,m+1,r,nowl,nowr)); return ans; } void insert(int x) { int temp=x%n+1; //1到n int ans=query(1,1,n,temp,n); //找到右边最小 if(ans==inf) //如果都是inf 表示不存在 ans=query(1,1,n,1,temp); //再找一次 Hash[ans-1]=x; update(1,1,n,ans); return; } int main() { int x; scanf("%d",&n); build(1,1,n); for(int i=0;i<n;i++) { scanf("%d",&x); insert(x); } for(int i=0;i<n;i++) { printf("%d",Hash[i]); if(i!=n-1) printf(" "); else printf("\n"); } return 0; }
全部评论
(2) 回帖