Queue
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1391 Accepted Submission(s): 709
Problem Description N people numbered from 1 to N are waiting in a bank for service. They all stand in a queue, but the queue never moves. It is lunch time now, so they decide to go out and have lunch first. When they get back, they don’t remember the exact order of the queue. Fortunately, there are some clues that may help.
Every person has a unique height, and we denote the height of the i -th person as hi . The i -th person remembers that there were ki people who stand before him and are taller than him. Ideally, this is enough to determine the original order of the queue uniquely. However, as they were waiting for too long, some of them get dizzy and counted ki in a wrong direction. ki could be either the number of taller people before or after the i -th person.
Can you help them to determine the original order of the queue?
Input The first line of input contains a number T indicating the number of test cases ( T≤1000 ).
Each test case starts with a line containing an integer N indicating the number of people in the queue ( 1≤N≤100000 ). Each of the next N lines consists of two integers hi and ki as described above ( 1≤hi≤109,0≤ki≤N−1 ). Note that the order of the given hi and ki is randomly shuffled.
The sum of N over all test cases will not exceed 106
Output For each test case, output a single line consisting of “Case #X: S”. X is the test case number starting from 1. S is people’s heights in the restored queue, separated by spaces. The solution may not be unique, so you only need to output the smallest one in lexicographical order. If it is impossible to restore the queue, you should output “impossible” instead.
Sample Input
3
3
10 1
20 1
30 0
3
10 0
20 1
30 0
3
10 0
20 0
30 1
Sample Output
Case #1: 20 10 30
Case #2: 10 20 30
Case #3: impossible
Source 2015 ACM/ICPC Asia Regional Hefei Online
Recommend wange2014
題意：t組資料，n個人，每個人有個身高h，和在他前面或者後面比他高的人數k，輸出滿足條件的最小字典序序列，沒有滿足條件的序列輸出impossible；
思路：首先不考慮字典序最小，那麼先把每個人按身高從小到大排序，每個人的位置就是他目前在從左往右的第k個空位或者從右往左的第k個空位，如果沒有這麼多空位則輸出impossible，再考慮字典序最小則是選擇每個數填在從左往右和從右往左的第k個位置靠左的那一個，這樣确定政策之後就好辦了，我們可以考慮用線段樹維護目前空位的個數，然後填上數字之後單點更新。主要是難得想，寫起來并不難~
AC代碼：
#include<iostream>
#include<cstring>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<string>
#include<algorithm>
#include<queue>
#include<cstdio>
#define LL long long
using namespace std;
priority_queue<LL,vector<LL>,greater<LL> > que,q;
int t;
struct node
{
int val;
int id;
}arr[100005];
int brr[100005];
bool cmp(node a,node b)
{
return a.val<b.val;
}
struct nn
{
int l;
int r;
int sum;//空位數
}segtree[100005*4];
void pushup(int root)
{
segtree[root].sum=segtree[root<<1].sum+segtree[root<<1|1].sum;
}
void build(int root,int l,int r)
{
segtree[root].l=l;
segtree[root].r=r;
if(l==r)
{
segtree[root].sum=1;
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
int query(int root,int id)
{
int ll=segtree[root].l;
int rr=segtree[root].r;
if(ll==rr)
return ll;
int mid=(ll+rr)>>1;
if(segtree[root<<1].sum>=id)
return query(root<<1,id);
else
return query(root<<1|1,id-segtree[root<<1].sum);
}
void update(int root,int p)
{
int ll=segtree[root].l;
int rr=segtree[root].r;
if(ll==rr)
{
segtree[root].sum=0;
return;
}
int mid=(ll+rr)>>1;
if(p<=mid)
update(root<<1,p);
else
update(root<<1|1,p);
pushup(root);
}
int main()
{
int t;
int cas=0;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&arr[i].val,&arr[i].id);
sort(arr+1,arr+1+n,cmp);//按身高排序
build(1,1,n);
int flag =0;
for(int i=1;i<=n;i++)
{
int tmp=arr[i].id+1;//tmp為要填在第幾個空位
if(arr[i].id+1>n-i+1-arr[i].id&&n-i+1-arr[i].id!=0)
tmp=n-i+1-arr[i].id;
if(segtree[1].sum<tmp)//沒有這麼多空格，直接結束
{
flag=1;
break;
}
int ans=query(1,tmp);
brr[ans]=arr[i].val;
update(1,ans);
}
printf("Case #%d: ",++cas);
if(flag)
printf("impossible\n");
else{
for(int i=1;i<=n;i++)
printf("%d%c",brr[i],i==n?'\n':' ');
}
}
return 0;
}