首页 > 代码库 > 【cogs247】售票系统

【cogs247】售票系统

2024-07-04 12:48:55   229人阅读

【问题描述】

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

【分析】

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

 

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 #include <vector>
 8 #define NEW(p) p=&mem[++size_point];p->from=0;p->to=0;p->cnt=p->lazy=0;p->left=NULL;p->right=NULL
 9 const int maxn=60000*2+100;
10 using namespace std;
11 struct node
12 {
13        int from,to,cnt,lazy;
14        node *left,*right;
15 }*root,mem[maxn];
16 int c,s,r,size_point=0;
17 
18 void make_tree(node *&t,int from,int to);
19 int count(node *&t,int from,int to);
20 void add(node *&t,int from,int to,int n);
21 void print(node *&t);
22 
23 int main()
24 {
25     int i;
26     
27     scanf("%d%d%d",&c,&s,&r);
28     make_tree(root,1,c);
29     for (i=1;i<=r;i++)
30     {
31         int u,v,n;
32         scanf("%d%d%d",&u,&v,&n);
33         v--;//注意是闭区间 
34         if (count(root,u,v)+n<=s) {printf("YES\n");add(root,u,v,n);}
35         else printf("NO\n");
36     }
37     return 0;
38 }
39 void make_tree(node *&t,int from,int to)
40 {
41      NEW(t);
42      if (from>to) return;
43      if (from==to) {t->from=from;t->to=to;return;}
44      t->from=from;t->to=to;
45      make_tree(t->left,from,(from+to)/2);
46      make_tree(t->right,((from+to)/2)+1,to);
47 }
48 void add(node *&t,int from,int to,int n)
49 {
50      if (from==t->from && to==t->to)
51      {
52          t->cnt+=n;
53          t->lazy+=n;
54          return;
55      }
56      if (t->lazy!=0)
57      {
58          t->left->cnt+=t->lazy;t->right->cnt+=t->lazy;
59          t->left->lazy+=t->lazy;t->right->lazy+=t->lazy;
60          t->lazy=0;
61      }
62      int mid=(t->from+t->to)/2;
63      if (to<=mid) add(t->left,from,to,n);
64      else if (mid<from) add(t->right,from,to,n);
65      else //分段 
66      {
67           add(t->left,from,mid,n);
68           add(t->right,mid+1,to,n);
69      }
70      t->cnt=max(t->left->cnt,t->right->cnt);
71 }
72 int count(node *&t,int from,int to)
73 {
74     if (from==t->from && to==t->to)
75     return t->cnt;
76     if (t->lazy!=0)
77     {
78          t->left->cnt+=t->lazy;t->right->cnt+=t->lazy;
79          t->left->lazy+=t->lazy;t->right->lazy+=t->lazy;
80          t->lazy=0;
81     }
82     int mid=(t->from+t->to)/2;
83     if (to<=mid) return count(t->left,from,to);
84     else if (mid<from) return count(t->right,from,to);
85     else //分段 
86     {
87           return 
88           max(count(t->left,from,mid),
89           count(t->right,mid+1,to));
90     }
91 }
92 void print(node *&t)//调试用 
93 {
94      if (t==NULL) return;
95      printf("%d %d %d\n",t->from,t->to,t->cnt);
96      print(t->left);
97      print(t->right);
98 }
View Code

 


联系
我们