正文

[usaco09feb]fairshuttle

NaVi_Awson  NaVi_Awson  2022-09-10  745

关键词：

Description

逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠N(1 ≤N≤20000)个地点（所有地点都以1到N之间的一个数字来表示）。现在奶牛们分成K(1≤K≤50000)个小组，第i 组有Mi(1 ≤Mi≤N)头奶牛，他们希望从Si跑到Ti(1 ≤Si<Ti≤N)。

由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是C(1≤C≤100)，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。

Input

第一行：包括三个整数：K，N和C，彼此用空格隔开。

第二行到K+1行：在第i+1行，将会告诉你第i组奶牛的信息：Si，Ei和Mi，彼此用空格隔开。

Output

第一行：可以坐班车的奶牛的最大头数。

Sample Input

Sample Output

Hint

班车可以把2头奶牛从1送到5，3头奶牛从5送到8，2头奶牛从8送到14，1头奶牛从9送到12，1头奶牛从13送到14，1头奶牛从14送到15。

题解

注意到可以不全部上车，那么贪心的思路就比较明确了。尽量让下车下得早的多上车，这样利益可以最大化。

我们按区间右端点排序。第i个区间[Li,Ri]显然我们要找到这个区间范围内已经累加的最大值，最大值可以用线段树维护，这里给出这种版本。

 1 #include<map>
 2 #include<set>
 3 #include<cmath>
 4 #include<ctime>
 5 #include<queue>
 6 #include<stack>
 7 #include<cstdio>
 8 #include<string>
 9 #include<vector>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define LL long long
15 #define RE register
16 #define IL inline
17 #define Lr (root<<1)
18 #define Rr (root<<1|1)
19  using namespace std;
20 const LL N=100000;
21 
22 LL k,n,c;
23 struct tt
24 {
25     LL l,r,c;
26 }a[N+5];
27 
28 LL smg[N*4+5],maxn[N*4+5];
29 LL Query(LL root,LL l,LL r,LL a,LL b);
30 void Add(LL root,LL l,LL r,LL a,LL b,LL key);
31 IL void Pushdown(LL root);
32 
33 bool comp(const tt &a,const tt &b){return a.r<b.r;}
34 IL LL Min(LL a,LL b){return a<b ? a:b;}
35 IL LL Max(LL a,LL b){return a>b ? a:b;}
36 
37 int main()
38 {
39     scanf("%lld%lld%lld",&k,&n,&c);
40     for (RE LL i=1;i<=k;i++)
41     {
42         scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].c);
43         a[i].r--;
44     }
45     sort(a+1,a+k+1,comp);
46     LL tmp,ans=0;
47     for (RE LL i=1;i<=k;i++)
48     {
49         tmp=Query(1,1,n,a[i].l,a[i].r);
50         if (tmp==c) continue;
51         ans+=Min(c-tmp,a[i].c);
52         Add(1,1,n,a[i].l,a[i].r,Min(c-tmp,a[i].c));
53     }
54     printf("%lld
",ans);
55     return 0;
56 }
57 
58 LL Query(LL root,LL l,LL r,LL a,LL b)
59 {
60     if (a<=l&&r<=b) return maxn[root];
61     Pushdown(root);
62     LL mid=(l+r)>>1;
63     LL ans=0;
64     if (mid>=a) ans=Query(Lr,l,mid,a,b);
65     if (mid<b) ans=Max(ans,Query(Rr,mid+1,r,a,b));
66     return ans;
67 }
68 void Add(LL root,LL l,LL r,LL a,LL b,LL key)
69 {
70     if (a<=l&&r<=b)
71     {
72         smg[root]+=key;
73         maxn[root]+=key;
74         return;
75     }
76     Pushdown(root);
77     LL mid=(l+r)>>1;
78     if (mid>=a) Add(Lr,l,mid,a,b,key);
79     if (mid<b) Add(Rr,mid+1,r,a,b,key);
80     maxn[root]=Max(maxn[Lr],maxn[Rr]);
81 }
82 IL void Pushdown(LL root)
83 {
84     smg[Lr]+=smg[root];maxn[Lr]+=smg[root];
85     smg[Rr]+=smg[root];maxn[Rr]+=smg[root];
86     smg[root]=0;
87 }

洛谷p1607[usaco09feb]庙会班车fairshuttle

题目描述AlthoughFarmerJohnhasnoproblemswalkingaroundthefairtocollectprizesorseetheshows,hiscowsarenotinsuchgoodshape;afulldayofwalkingaroundthefairleavesthemexhausted.Tohelpthemenjoythefair,FJhasarrangedf 查看详情

[usaco09feb]fairshuttle

Description逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代... 查看详情

bzoj1577[usaco09feb]fairshuttle

题目大意：n个站点，有m群奶牛,第i群奶牛有mi只，要从si站点出发，直到ti站点下车。对于一群奶牛，可以不全部上车。同时在车上的奶牛数不能超过c,求最多能满足多少头奶牛的要求。注意到可以不全部上车，那么贪心的思... 查看详情

[usaco09feb]庙会班车fairshuttle

题目描述逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代... 查看详情

[usaco2009feb]庙会捷运fairshuttle

Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）只奶牛。而且不走重... 查看详情

[bzoj1577][usaco2009feb]庙会捷运fairshuttle_贪心_线段树

庙会捷运FairShuttlebzoj-1577Usaco-2009Feb题目大意：有一辆公交车从1走到n。有m群奶牛从$S_i$到$E_i$，第i群奶牛有$W_i$只。车有一个容量c。问不走回头路的情况下最多使多少奶牛到达目的地。其中，每一群奶牛不一定都拉走。注释：$1le... 查看详情

bzoj1577:[usaco2009feb]庙会捷运fairshuttle

n<=20000个车站，车能同时载C<=100个人，求能满足K<=50000群人的多少个。每群人给起点终点和人数，一群人不一定要都满足。一开始想DP，想不出，很菜。贪心即可。如果有右端点相同的几群人，那肯定优先满足左端点大的；... 查看详情

贪心bzoj1577:[usaco2009feb]庙会捷运fairshuttle(代码片段)

一类经典的线段贪心Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）... 查看详情

bzoj1577:[usaco2009feb]庙会捷运fairshuttle——小根堆+大根堆+贪心

[usaco09feb]改造路revampingtrails

题目描述FarmerJohndutifullychecksonthecowseveryday.HetraversessomeoftheM(1<=M<=50,000)trailsconvenientlynumbered1..Mfrompasture1allthewayouttopastureN(ajourneywhichisalwayspossiblefortrailmapsgiveni 查看详情

[usaco09feb]改造路revampingtrails

洛谷p2939[usaco09feb]改造路revampingtrails(代码片段)

p2939[usaco09feb]改造路revampingtrails(代码片段)

传送门显然的分层图设dis[i][j]表示到点i，已经建立了j条高速公路的最短距离然后转移每次都分建立高速公路和不建立高速公路两种情况跑Djikstra#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmat... 查看详情

luogup2939[usaco09feb]改造路revampingtrails

约翰一共有N)个牧场.由M条布满尘埃的小径连接.小径可以双向通行.每天早上约翰从牧场1出发到牧场N去给奶牛检查身体.通过每条小径都需要消耗一定的时间.约翰打算升级其中K条小径，使之成为高速公路.在高速公路上的通行几乎... 查看详情

[usaco2009febgold]fairshuttle(贪心+优先队列)(代码片段)

题目大意：有N个站点的轻轨站，有一个容量为C的列车起点在1号站点，终点在N号站点，有K组牛群，每组数量为Mi（1≤Mi≤N），行程起点和终点分别为Si和Ei（1≤Si<Ei≤N）。计算最多有多少头牛可以搭乘轻轨。一道经典的贪心... 查看详情

[jloi2011]飞行路线&[usaco09feb]revampingtrails

DescriptionAlice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从... 查看详情

[usaco15feb]censoring

DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情

洛谷p3663[usaco17feb]whydidthecowcrosstheroadiiis

P3663[USACO17FEB]WhyDidtheCowCrosstheRoadIIIS题目描述Whydidthecowcrosstheroad?Well,onereasonisthatFarmerJohn‘sfarmsimplyhasalotofroads,makingitimpossibleforhiscowstotravelaroundwithoutcrossingmanyofthem.为查看详情