首页 > 代码库 > p1245 售票系统(线段树)
p1245 售票系统(线段树)
题目描述:
某次列车途经C个城市,城市编号依次为1到C,列车上共有S个座位,铁路局规定售出的车票只能是坐票, 即车上所有的旅客都有座。售票系统是由计算机执行的,每一个售票申请包含三个参数,分别用O、D、N表示,O为起始站,D为目的地站,N为车票张数。售票 系统对该售票申请作出受理或不受理的决定,只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序,实现这个自动 售票系统。
输入格式:
第一行包含三个用空格隔开的整数C、S和R,其中1≤C≤60000, l≤S≤60000,1≤R≤60000。C为城市个数,S为列车上的座位数,R为所有售票申请总数。接下来的R行每行为一个售票申请,用三个由空格隔开的整数O,D和N表示,O为起始站,D 为目的地站,N为车票张数,其中1≤D≤C,1≤O≤C,所有的售票申请按申请的时间从早到晚给出。
输出格式:
输出共有R行,每行输出一个“YES”或“NO”,表示当前的售票申请被受理或不被受理。
样例输入:
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3
样例输出:
YES
YES
NO
NO
思路:
这道题就是线段树最基本的操作问题,每输入一个售票申请,就先将这个区间内的售票的数量增加,在查找这个区间内的总售票数量,如果总售票数量大于人数则输出NO
(注意:如果输出NO的话说明这个售票申请不合法,那么就直接去掉这个请求所增加的售票数)反正输出YES即可
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int c,s,r,x,y,v; struct haha { int maxx; int delta; }tree[500000]; void updata(int left,int right,int root) { int mid; if((y<left||x>right)) return; if(x<=left&&y>=right) { tree[root].maxx+=v; tree[root].delta+=v; return; } mid=(left+right)/2; int del=tree[root].delta; tree[root*2].delta+=del; tree[root*2].maxx+=del; tree[root*2+1].delta+=del; tree[root*2+1].maxx+=del; tree[root].delta=0; updata(left,mid,root*2); updata(mid+1,right,root*2+1); tree[root].maxx=max(tree[root*2].maxx,tree[root*2+1].maxx); } int search(int left,int right,int root) { int mid,templ,tempr; if(x>right||y<left) return -200000; if(x<=left&&right<=y) return tree[root].maxx; mid=(left+right)/2; int del=tree[root].delta; tree[root*2].delta+=del; tree[root*2].maxx+=del; tree[root*2+1].delta+=del; tree[root*2+1].maxx+=del; tree[root].delta=0; templ=search(left,mid,root*2); tempr=search(mid+1,right,root*2+1); return max(templ,tempr); } int main() { //freopen("add.in","r",stdin); //freopen("add.out","w",stdout); cin>>c>>s>>r; for(int i=1;i<=r;i++) { int o,d,n; cin>>o>>d>>n; x=o; y=d-1; v=n; updata(1,c,1); int t=search(1,c,1); if(t<=s) cout<<"YES"<<endl; else { cout<<"NO"<<endl; v=-n; updata(1,c,1);//把不合法的售票请求去掉 } } return 0; }
p1245 售票系统(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。