2017.10.3 国庆清北 D3T2 公交车

题目描述

LYK在玩一个游戏。

有k群小怪兽想乘坐公交车。第i群小怪兽想从xi出发乘坐公交车到yi。但公交车的容量只有M，而且这辆公交车只会从1号点行驶到n号点。

LYK想让小怪兽们尽可能的到达自己想去的地方。它想知道最多能满足多少小怪兽的要求。

当然一群小怪兽没必要一起上下车，它们是可以被分开来的。

输入输出格式

输入格式：

第一行三个数k,n,M。

接下来k行每行3个数xi，yi和ci。其中ci表示第i群小怪兽的小怪兽数量。

输出格式：

一个数表示最多有多少只小怪兽能满足要求。

输入输出样例

输入样例#1：

输出样例#1：

5

样例解释
第一群的3只小怪兽在1号点上车，并在3号点下车。
第二群的2只小怪兽在3号点上车，5号点下车。

说明

对于30%的数据小怪兽的总数不超过10只，n<=10。

对于另外30%的数据k,n<=1000。

对于100%的数据1<=n<=20000，1<=k<=50000，1<=M<=100，1<=ci<=100，1<=xi<yi<=n。

  1 /*luogu上做过的原题。USACO的庙会班车，做线段树的那段时间看过，一眼认出是原题，毕竟看过好几次。
  2 
  3 贪心+线段树
  4  
  5 类似于活动安排，先按右端点排个序，然后线段树维护区间最大值就好了。
  6 为什么呢。
  7 因为一段路上公交车中还能坐下的最大的人数为 容量-这段路上车内人数的最大值。
  8 所以，用线段树维护区间最大值，在小怪物上车的时候查询坐车的这段区间的最大值，
  9 然后用容量-得到的最大值，就是能上车的人数。 
 10 遵循能上多少是多少的原则，这样得出来肯定是最优解。
 11 需要注意的是，updata的时候是更新到node[i].r-1,因为node[i].r的时候上车的那群小怪物已经下车了。 
 12 */
 13 
 14 #include<iostream>
 15 #include<cmath>
 16 #include<cstdio>
 17 #include<cstring>
 18 #include<algorithm>
 19 #define N 50005
 20 #define lson (root<<1)
 21 #define rson (root<<1|1)
 22 #define _max(a,b) a=a>b?a:b
 23 using namespace std;
 24 
 25 int k,n,m,x,y,ans,tmp,val;
 26 int tree[N<<2],mark[N<<2];
 27 struct Node
 28 {
 29     int l,r,peo;
 30     bool operator <(const Node &a)const
 31     {
 32         if(a.r!=r)return r<a.r;
 33         return l>a.l;
 34     }
 35 }node[N];
 36 
 37 inline void read(int &num)
 38 {
 39     char c=getchar();
 40     for(;!isdigit(c);c=getchar());
 41     for(;isdigit(c);c=getchar()){num=num*10+c-'0';};
 42 }
 43 
 44 void pushdown(int root)
 45 {
 46     if(!mark[root]) return;
 47     int k=mark[root];
 48     tree[lson]+=k;tree[rson]+=k;
 49     mark[lson]+=k;mark[rson]+=k;
 50     mark[root]=0;
 51 }
 52 
 53 int query(int root,int l,int r,int L,int R)
 54 {
 55     if(l>R||r<L) return 0;
 56     if(L<=l&&r<=R) return tree[root];
 57     int mid=(l+r)>>1;
 58     pushdown(root);
 59     int a=query(lson,l,mid,L,R),b=query(rson,mid+1,r,L,R);
 60     tree[root]=_max(tree[lson],tree[rson]);
 61     return _max(a,b);
 62 }
 63 
 64 void updata(int root,int l,int r,int L,int R,int to)
 65 {
 66     if(l>R||r<L) return;
 67     if(L<=l&&r<=R)
 68     {
 69         mark[root]+=to;
 70         tree[root]+=to;
 71         return;
 72     }
 73     pushdown(root);
 74     int mid=(l+r)>>1;
 75     updata(lson,l,mid,L,R,to);
 76     updata(rson,mid+1,r,L,R,to);
 77     tree[root]=_max(tree[lson],tree[rson]);
 78 }
 79 
 80 void init()
 81 {
 82     read(k),read(n),read(m);
 83     for(int i=1;i<=k;i++)
 84     {
 85         read(node[i].l),read(node[i].r),read(node[i].peo);
 86     }
 87     sort(node+1,node+k+1);
 88     for(int i=1;i<=k;i++)
 89     {
 90         tmp=query(1,1,n,node[i].l,node[i].r);
 91         if(tmp>=m) continue;    //最大值超过了容量，一个人也坐不下了 
 92         if(tmp+node[i].peo<=m) val=node[i].peo;        //当前这群小怪物可以全部坐下 
 93         else val=m-tmp;        //不能全坐下，能坐几个算几个 
 94         ans+=val;
 95         updata(1,1,n,node[i].l,node[i].r-1,val);    //是到r-1,不是r！ 
 96     }
 97     printf("%d",ans);
 98 }
 99 
100 int main()
101 {
102     freopen("bus.in","r",stdin);
103     freopen("bus.out","w",stdout);
104     init();
105     fclose(stdin);
106     fclose(stdout);
107     return 0;
108 }

View Code