这题开始的思路就是模拟:就像数组中插点一样,每一个想买票的人都想往前插队!
但是这样的话肯定TLE, 看了别人的思路之后才恍然大悟!
正解:
将开始的正序插入,变成倒序插入,这样的话,想一想:第 i 个人想要插在 p[i]
的位置上,那么就要保证所插入的位置之前一定要有 p[i]-1个空位!因为一定会有p[j]<p[i]
(0<=p[j]<=j,每个人都想往前插队)
的第j个人插在p[i]的位置的前边!
如果i<j; && p[i]==p[j], 倒序插入中,第j个人先插入, 那么第i个人在保证插入的位置之前有
p[i]-1个空位的同时,又要插入到第 j 个人的后边!
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define M 200005
using namespace std;
pair<int, int>per[M];
int ret[M];
int tree[M*4];
int n;
void buildT(int p, int ld, int rd){
if(ld==rd){
tree[p]=1;
return ;
}
int mid=(ld+rd)>>1;
buildT(p<<1, ld, mid);
buildT(p<<1|1, mid+1, rd);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
void updateT(int p, int ld, int rd, int pos, int val){
if(ld==rd){
tree[p]=0;
ret[ld]=val;
return ;
}
int mid=(ld+rd)>>1;
if(tree[p<<1]>pos)
updateT(p<<1, ld, mid, pos, val);
else
updateT(p<<1|1, mid+1, rd, pos-tree[p<<1], val);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
int main(){
int i;
while(scanf("%d", &n)!=EOF){
buildT(1, 1, n);
for(i=1; i<=n; ++i)
scanf("%d%d", &per[i].first, &per[i].second);
for(i=n; i>=1; --i)
updateT(1, 1, n, per[i].first, per[i].second);
printf("%d", ret[1]);
for(i=2; i<=n; ++i)
printf(" %d", ret[i]);
printf("\n");
}
return 0;
}
本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3885134.html,如需转载请自行联系原作者