首页 > 代码库 > p1245 售票系统（线段树）

p1245 售票系统（线段树）

2024-09-10 16:55:00   247人阅读

题目描述：

某次列车途经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 售票系统（线段树）


联系
我们