本文主要是介绍【POJ】Buy Tickets（思路 + 线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一开始没有思路，之后问了一下学长，需要逆向处理输入。
最后一个加入队列的肯定是没有冲突的，所以我们可以从最后一个开始处理，从后往前，找第 i + 1个空着的地方。
线段树的话记录 区间中 空白位置的个数。
| 13441833 | 201301052100 | 2828 | Accepted | 5368K | 1704MS | C++ | 1690B | 2014-09-14 21:19:45 |
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
/*=====================================*/
const int maxn = 200000 + 10;
int tree[maxn << 2];
int ans[maxn << 2];
int array[maxn],value[maxn];
int n;
void BuildTree(int L,int R,int pos){if(L == R){tree[pos] = 1; //在区间L，R之间有几个空位return ;}int m = (L + R) >> 1;BuildTree(L,m,pos << 1);BuildTree(m + 1, R ,(pos << 1)|1);tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];return ;
}
void UpDate(int k,int L,int R,int pos,int value){if(L == R){ans[pos] = value;tree[pos] --;return ;}int m = (L + R) >> 1;int e1 = tree[pos << 1];int e2 = tree[(pos << 1)|1];if(e1 >= k)UpDate(k,L,m,pos << 1,value);elseUpDate(k - e1,m + 1,R, (pos << 1)|1,value);tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];
}
void ShowTree(int L,int R,int pos){if(L == R){printf("%d",ans[pos]);return ;}int m = (L + R) >> 1;ShowTree(L, m, pos << 1);printf(" ");ShowTree(m + 1, R ,(pos << 1)|1);
}
int main(){while(scanf("%d",&n) != EOF){BuildTree(1,n,1); //log(n)的时间复杂度建树for(int i = 0 ; i < n ; i++)scanf("%d%d",&array[i],&value[i]);for(int i = n - 1 ; i >= 0 ; i --){ //找到第 i + 1个为空的位置UpDate(array[i] + 1,1,n,1,value[i]); //nlog(n)的时间复杂度进行更新}ShowTree(1,n,1); //log(n)的时间复杂度打印路径printf("\n");}return 0;
}
这篇关于【POJ】Buy Tickets（思路 + 线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
