程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj-2828 Buy Tickets

poj-2828 Buy Tickets

編輯：C++入門知識

poj-2828 Buy Tickets

題意：有n個的排隊，每一個人都有一個val來對應，每一個後來人都會插入當前隊伍的某一個位置pos。要求把隊伍最後的狀態輸出。

逆向思考。這樣考慮，最後一個人一定會得到當前隊伍他想要的位置，如果我們往前一個階段，倒數第二個人也一定能得到他想要的位置……，也就是說，我們可以這樣處理，我們把最後一個人插入，然後忽略它，再把倒數第二個人插入。即，我們找出當前隊伍他想要插入的位置pos的真正坐標就可以。然後去更新整個隊伍的長度。如此循環，直到最後一個人。線段樹在單點更新的時候，感覺和二分查找是很相似的，可以用它實現。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 

#define Mid(a,b) ( a+((b-a)>>1))
#define ll(x) (x<<1)
#define rr(x) (x<<1|1)

const int N = 200010;

using namespace std;

int n;
int pos[N];
int val[N];
int ans[N];

struct node
{
	int left;
	int right;
	int sum;
	int mid() { return Mid(left, right); }
};

struct segtree
{
	node tree[N * 4];
	void buildtree(int left,int right,int ind)
	{
		tree[ind].left = left;
		tree[ind].right = right;
		
		tree[ind].sum = right - left + 1;
		
		if (left !=right)
		{
			int mid = tree[ind].mid();
			buildtree(left,mid,ll(ind));
			buildtree(mid+1,right,rr(ind));
		}
	}
	
	int query(int val,int pos)
	{
		int left = tree[pos].left;
		int right = tree[pos].right;

		if (left == right)
		{
			tree[pos].sum = 0;
			return left;
		}
		else
		{
			int ind;
			if (tree[ll(pos)].sum >= val)
				ind = query(val, ll(pos));
			else
				ind = query(val - tree[ll(pos)].sum , rr(pos));

			tree[pos].sum = tree[ll(pos)].sum + tree[rr(pos)].sum;

			return ind;
		}
	}
}seg;

int main()
{
	while (scanf(%d,&n)!=EOF)
	{
		seg.buildtree(1,n,1);

		for (int i = 1; i <= n; i++)
		{
			scanf(%d %d,&pos[i],&val[i]);
		}

		for(int i = n; i >=1; i--)
		{
			int ps = seg.query(pos[i]+1,1);
			ans[ps] = val[i];
		}

		for (int i = 1; i <= n; i++)
		{
			printf(%d,ans[i]);
			if (i != n)
				printf( );
		}
		printf(
);
	}
	return 0;
}