1291 火车线路
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
查看运行结果
题目描述 Description
某列火车行使在C个城市之间(出发的城市编号为1，结束达到的城市的编号为C)，假设该列火车有S个座位，现在有R笔预订票的业务。现在想对这R笔业务进行处理，看哪些预定能满足，哪些不能满足。
一笔预定由O、D、N三个整数组成，表示从起点站O到目标站D需要预定N个座位。一笔预定能满足是指该笔业务在行程范围内有能满足的空座位，否则就不能满足。一笔业务不能拆分，也就是起点和终点站不能更改，预定的座位数目也不能更改。所有的预定需求按给出先后顺序进行处理。
请你编写程序，看那些预定业务能满足，那些不能满足。
输入描述 Input Description
输入文件中的第一行为三个整数C、S、R，(1<=c<=60 000, 1<=s<=60 000, 1<=r<=60 000)他们之间用空隔分开。接下来的R行每行为三个整数O、D、N，(1<=o<d<=c, 1<=n<=s)，分别表示每一笔预定业务。
输出描述 Output Description
对第I笔业务，如果能满足，则在输出文件中的第I行输出“T”，否则输出“N”
样例输入 Sample Input
4 6 41 4 21 3 22 4 31 2 3
样例输出 Sample Output
TTNN‘
’mmzz题目有毒。。。
本来就是个裸地线段树记录最小值。
结果误解他题目了，。
调了三个小时
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define ls k<<1
8 #define rs k<<1|1
9 using namespace std;
10 const int MAXN=2000001;
11 void read(int &n)
12 {
13 char c='+';int x=0;bool flag=0;
14 while(c<'0'||c>'9')
15 {c=getchar();if(c=='-')flag=1;}
16 while(c>='0'&&c<='9')
17 {x=x*10+c-48,c=getchar();}
18 flag==1?n=-x:n=x;
19 }
20 int n,m,chair;
21 int ans=-1;
22 struct node
23 {
24 int l,r,w,fm;
25 }tree[MAXN*4];
26 void update(int k)
27 {
28 tree[k].w=min(tree[ls].w,tree[rs].w);
29
30 }
31 void pushdown(int k)
32 {
33 tree[ls].w-=tree[k].fm;
34 tree[rs].w-=tree[k].fm;
35 tree[ls].fm+=tree[k].fm;
36 tree[rs].fm+=tree[k].fm;
37 tree[k].fm=0;
38 //cout<<"ls:"<<(ls)<<" "<<tree[ls].w<<" ";
39 //cout<<"rs:"<<(rs)<<" "<<tree[rs].w<<" "<<endl;
40 }
41 void build_tree(int ll,int rr,int k)
42 {
43 tree[k].l=ll;tree[k].r=rr;
44 if(ll==rr)
45 {
46 tree[k].w=chair;
47 return ;
48 }
49 int mid=(ll+rr)>>1;
50 build_tree(ll,mid,ls);
51 build_tree(mid+1,rr,rs);
52 update(k);
53 }
54 void interval_ask(int ll,int rr,int num,int k)
55 {
56 if(ll>tree[k].r||rr<tree[k].l)
57 return ;
58 if(ll<=tree[k].l&&tree[k].r<=rr)
59 {
60 if(tree[k].w<num)
61 ans=-1;
62 return ;
63 }
64 int mid=(tree[k].l+tree[k].r)>>1;
65 if(tree[k].fm)
66 pushdown(k);
67 if(ll<=mid)
68 interval_ask(ll,rr,num,ls);
69 if(rr>mid)
70 interval_ask(ll,rr,num,rs);
71 if(tree[k].fm)
72 pushdown(k);
73 }
74 void point_change(int pos,int v,int k)
75 {
76 if(pos>tree[k].r||pos<tree[k].l)
77 return ;
78 if(tree[k].l==tree[k].r)
79 {
80 tree[k].w=v;
81 return ;
82 }
83 point_change(pos,v,ls);
84 point_change(pos,v,rs);
85 update(k);
86 }
87
88 void interval_change(int ll,int rr,int num,int k)
89 {
90 if(ll>tree[k].r||rr<tree[k].l)
91 return ;
92 if(ll<=tree[k].l&&rr>=tree[k].r)
93 {
94 tree[k].w-=num;
95 tree[k].fm+=num;
96 return ;
97 }
98 int mid=(tree[k].l+tree[k].r)>>1;
99 if(tree[k].fm)
100 pushdown(k);
101 if(ll<=mid)
102 interval_change(ll,rr,num,ls);
103 if(rr>mid)
104 interval_change(ll,rr,num,rs);
105 update(k);
106 }
107 int main()
108 {
109 read(n);read(chair);read(m);
110 build_tree(1,n,1);
111 for(int i=1;i<=m;i++)
112 {
113 int l,r,num;
114 ans=1;
115 read(l);read(r);read(num);
116 r--;
117 interval_ask(l,r,num,1);
118 if(ans!=1)
119 printf("N\n");
120 else
121 {
122 interval_change(l,r,num,1);
123 printf("T\n");
124 }
125 }
126 return 0;
127 } 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-07-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
