首页 > 代码库 > 售票系统

售票系统

售票系统

时间限制: 1 Sec  内存限制: 128 MB

题目描述

某次列车途经C个城市,城市编号依次为1到C,列车上共有S个座位,铁路局规定售出的车票只能是坐票,即车上所有的旅客都有座,售票系统是由计算机执行的,每一个售票申请包含三个参数,分别用O、D、N表示,O为起始站,D为目的地站,N为车票张数,售票系统对该售票申请作出受理或不受理的决定,只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理,请你写一个程序,实现这个自动售票系统。

 

输入

输入文件第一行包含三个用空格隔开的整数C、S和R,其中1<=C<=60000,1<=S<=60000,1<=R<=60000,C为城市个数,S为列车上的座位数,R为所有售票申请总数。接下来的R行每行为一个售票申请,用三个由空格隔开的整数O,D和N表示,O为起始站,D为目的地站,N为车票张数,其中1<=0<D<=C,1<=N<=S,所有的售票申请按申请的时间从早到晚给出。

 

输出

输出文件共有R行,每行输出一个“YES”或“NO”,表示当前的售票申请被受理或不被受理。

 

样例输入

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

样例输出

YES
YES
NO
NO
 
题解:
维护一个线段树保存区间最小值,定义一个judge函数判断是否能够受理申请,若可以就进行修改并输出YES,若不可以就直接输出NO。
此题比较坑的是题目中说“O为起始站,D为目的地站”,所以要n--,r--。
题目比较简单,不过多阐述,以下是AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<stack>
#include<queue>
#include<ctime>
using namespace std;
const int maxn=60005;
int ll(int x){return x<<1;}
int rr(int x){return x<<1|1;}
int n,m,s;
int sgm[maxn*7],root,lazy[maxn*7];
void build(int root,int left,int right)
{
    if(left==right)
    {
        sgm[root]=s;
        return;
    }
    int m=(left+right)>>1;
    build(ll(root),left,m);
    build(rr(root),m+1,right);
    sgm[root]=min(sgm[ll(root)],sgm[rr(root)]);
}
void pushdown(int root)
{
    lazy[ll(root)]+=lazy[root];
    lazy[rr(root)]+=lazy[root];
    sgm[ll(root)]-=lazy[root];
    sgm[rr(root)]-=lazy[root];
    lazy[root]=0;
}
bool judge(int root,int left,int right,int l,int r,int x)
{
    if(l<=left&&right<=r)
    {
        if(sgm[root]>=x)return 1;
        else return 0;
    }
    int m=(left+right)>>1;
    bool ans=1;
    if(lazy[root])pushdown(root);
    if(l<=m)ans=ans&&judge(ll(root),left,m,l,r,x);
    if(m<r)ans=ans&&judge(rr(root),m+1,right,l,r,x);
    return ans;
}
void insert(int root,int left,int right,int l,int r,int x)
{
    if(l<=left&&right<=r)
    {
        lazy[root]+=x;
        sgm[root]-=x;
        return;
    }
    if(l>right||r<left)return;
    int m=(left+right)>>1;
    if(l<=m)insert(ll(root),left,m,l,r,x);
    if(m<r)insert(rr(root),m+1,right,l,r,x);
    sgm[root]=min(sgm[ll(root)],sgm[rr(root)]);
}
int main()
{
    int i,j,l,r;
    scanf("%d%d%d",&n,&s,&m);
    build(1,1,n);
    n--;
    root=1;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&l,&r,&j);
        r--;
        if(judge(root,1,n,l,r,j))
        {
            printf("YES\n");
            insert(root,1,n,l,r,j);
        }
        else printf("NO\n");
    }
    return 0;
}

 

售票系统