首页 > 代码库 > 1291 火车线路

1291 火车线路

2024-10-19 18:20:02   212人阅读

 时间限制: 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 4
1 4 2
1 3 2
2 4 3

1 2 3

样例输出 Sample Output
T
T
N

N‘

’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 }

 

1291 火车线路


联系
我们