当前位置:首页 > 开发 > 移动开发 > 正文

POJ-2828-Buy Tickets

发表于: 2012-08-07   作者:aijuans   来源:转载   浏览:
摘要: POJ-2828-Buy Tickets http://poj.org/problem?id=2828 线段树,逆序插入 #include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;#define N 200010struct

POJ-2828-Buy Tickets

http://poj.org/problem?id=2828

线段树,逆序插入

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;#define N 200010struct cam{	int x,y;	int num;}list[N*8];int pos[N],value[N],ans[N];int n;void build(int k,int x,int y)  //用线段树存储区间内还有多少位子没有被占{	list[k].x=x;	list[k].y=y;	list[k].num=(y-x+1);	if(x==y)	return;	int mid;	mid=(x+y)/2;	build(k<<1,x,mid);	build(k<<1|1,mid+1,y);}void find(int k,int pos,int value){	list[k].num--;	if(list[k].x==list[k].y)	{		ans[list[k].x]=value;		return;	}	if(list[k<<1].num>=pos)	find(k<<1,pos,value);	else	find(k<<1|1,pos-list[k<<1].num,value);}int main(){	int i;	while(scanf("%d",&n)!=EOF)	{		for(i=1;i<=n;i++)		scanf("%d%d",&pos[i],&value[i]);		build(1,1,n);		for(i=n;i>=1;i--)		find(1,pos[i]+1,value[i]);		for(i=1;i<=n;i++)		{			if(i==n)			printf("%d\n",ans[i]);			else			printf("%d ",ans[i]);		}	}	return 0;}


POJ-2828-Buy Tickets

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Description Railway tickets were difficult to buy around the Lunar New Year in China, so we m
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 10858 Accepted: 5272 D
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 10862 Accepted: 5273 D
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 7553 Accepted: 3599 De
Description Railway tickets were difficult to buy around the Lunar New Year in China, so we m
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 16584 Accepted: 8268 D
点击打开题目链接 Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 10042
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 9712 Accepted: 4679 De
Description Railway tickets were difficult to buy around the Lunar New Year in China, so we m
http://poj.org/problem?id=2828 一开始敲了个splay,直接模拟。 tle了。。 常数太大。。 好吧,说
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号