【cogs247】售票系统

【问题描述】

某次列车途经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”，表示当前的售票申请被受理或不被受理。

【分析】

线段树的应用，记录区间最大值，标记下传。

 #include <cstdlib>

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <queue>

 #include <vector>

 #define NEW(p) p=&mem[++size_point];p->from=0;p->to=0;p->cnt=p->lazy=0;p->left=NULL;p->right=NULL

 const int maxn=*+;

 using namespace std;

 struct node

 {

        int from,to,cnt,lazy;

        node *left,*right;

 }*root,mem[maxn];

 int c,s,r,size_point=;

 void make_tree(node *&t,int from,int to);

 int count(node *&t,int from,int to);

 void add(node *&t,int from,int to,int n);

 void print(node *&t);

 int main()

 {

     int i;

     scanf("%d%d%d",&c,&s,&r);

     make_tree(root,,c);

     for (i=;i<=r;i++)

     {

         int u,v,n;

         scanf("%d%d%d",&u,&v,&n);

         v--;//注意是闭区间

         if (count(root,u,v)+n<=s) {printf("YES\n");add(root,u,v,n);}

         else printf("NO\n");

     }

     return ;

 }

 void make_tree(node *&t,int from,int to)

 {

      NEW(t);

      if (from>to) return;

      if (from==to) {t->from=from;t->to=to;return;}

      t->from=from;t->to=to;

      make_tree(t->left,from,(from+to)/);

      make_tree(t->right,((from+to)/)+,to);

 }

 void add(node *&t,int from,int to,int n)

 {

      if (from==t->from && to==t->to)

      {

          t->cnt+=n;

          t->lazy+=n;

          return;

      }

      if (t->lazy!=)

      {

          t->left->cnt+=t->lazy;t->right->cnt+=t->lazy;

          t->left->lazy+=t->lazy;t->right->lazy+=t->lazy;

          t->lazy=;

      }

      int mid=(t->from+t->to)/;

      if (to<=mid) add(t->left,from,to,n);

      else if (mid<from) add(t->right,from,to,n);

      else //分段

      {

           add(t->left,from,mid,n);

           add(t->right,mid+,to,n);

      }

      t->cnt=max(t->left->cnt,t->right->cnt);

 }

 int count(node *&t,int from,int to)

 {

     if (from==t->from && to==t->to)

     return t->cnt;

     if (t->lazy!=)

     {

          t->left->cnt+=t->lazy;t->right->cnt+=t->lazy;

          t->left->lazy+=t->lazy;t->right->lazy+=t->lazy;

          t->lazy=;

     }

     int mid=(t->from+t->to)/;

     if (to<=mid) return count(t->left,from,to);

     else if (mid<from) return count(t->right,from,to);

     else //分段

     {

           return

           max(count(t->left,from,mid),

           count(t->right,mid+,to));

     }

 }

 void print(node *&t)//调试用

 {

      if (t==NULL) return;

      printf("%d %d %d\n",t->from,t->to,t->cnt);

      print(t->left);

      print(t->right);

 }

巴特西

【cogs247】售票系统

【问题描述】

【输入格式】

【输出格式】

最新文章

热门文章