关键词：
题目大意：n个站点，有m群奶牛,第i群奶牛有mi只，要从si站点出发，直到ti站点下车。
对于一群奶牛，可以不全部上车。同时在车上的奶牛数不能超过c,求最多能满足多少头奶牛的要求。
注意到可以不全部上车，那么贪心的思路就比较明确了
尽量让下车下得早的多上车，这样利益可以最大化
某些细节还是挺磨人的
1 #include<cstdio> 2 #include<cstdlib> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 #include<set> 7 #define be *S.begin() 8 #define ed *S.rbegin() 9 #define vv G[i][j].first 10 #define ww G[i][j].second 11 using namespace std; 12 const int N=50010; 13 int k,n,c; 14 vector<pair<int,int> > G[N]; 15 set<int> S; 16 int t[N]; 17 int main(){ 18 #ifndef ONLINE_JUDGE 19 freopen("fs.in","r",stdin);freopen("fs.out","w",stdout); 20 #endif 21 scanf("%d%d%d",&k,&n,&c); 22 while(k--){ 23 int u,v,w; 24 scanf("%d%d%d",&u,&v,&w); 25 G[u].push_back(make_pair(v,w)); 26 } 27 for(int i=1;i<=n;++i)sort(G[i].begin(),G[i].end()); 28 int ans=0,in_car=0; 29 for(int i=1;i<=n;++i){ 30 int j=0,j_end=G[i].size(); 31 if(!S.empty()&&be==i){ 32 ans+=t[be];in_car-=t[be]; 33 S.erase(be); 34 }//calc the number of the satisfy cow 35 for(;j<j_end&&in_car<c;++j){ 36 int go_into=min(c-in_car,ww); 37 t[vv]+=go_into;in_car+=go_into;ww-=go_into; 38 S.insert(vv); 39 if(in_car==c)break; 40 }//get on the red bus or blablabla,if the bus can be filled,fill it 41 for(;j<j_end&&vv<ed;++j) 42 while(!S.empty()&&ww){ 43 int go_into=min(ww,t[ed]); 44 t[ed]-=go_into,t[vv]+=go_into; 45 S.insert(vv); 46 if(!t[ed])S.erase(ed); 47 ww-=go_into; 48 }//sacrifice others‘ advantage to get the best advantage 49 } 50 printf("%d ",ans); 51 return 0; 52 }
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——小根堆+大根堆+贪心
Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）只奶牛。而且不走重... 查看详情
bzoj1577usaco2009febgold1.fairshuttlesolution
权限题，不给传送门啦！在学校OJ上交的.. 有些不开心，又是一道贪心，又是一个高级数据结构的模板，又是看了别人的题解还写崩了QAQ，蒟蒻不需要理由呀。 正经题解：首先，我们可以由「显然成立法」得出，只要我... 查看详情
[bzoj2591][usaco2012feb]nearbycows
2591:[Usaco2012Feb]NearbyCowsTimeLimit:4Sec MemoryLimit:128MBSubmit:149 Solved:89[Submit][Status][Discuss]Description FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfi 查看详情
bzoj3942:[usaco2015feb]censoring
3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBSubmit: 404 Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情
bzoj3940[usaco2015feb]censoring
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情
bzoj1651:[usaco2006feb]stallreservations专用牛棚
二次联通门: BZOJ1651:[Usaco2006Feb]StallReservations专用牛棚 权限题放题面DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA.. 查看详情
[bzoj]1631:[usaco2007feb]cowparty
1631:[Usaco2007Feb]CowPartyTimeLimit:5Sec MemoryLimit:64MBSubmit:866 Solved:624[Submit][Status][Discuss]Description 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X 查看详情
bzoj4412[usaco2016feb]circularbarn
先看成一条链for一遍找位置在for一遍算答案#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cmath>usingnamespacestd;typedeflonglongLL;#def 查看详情
[bzoj]1651:[usaco2006feb]stallreservations专用牛棚
1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit:10Sec MemoryLimit:64MBSubmit:987 Solved:566[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N<=50,000)cows!Theyaresopi 查看详情
[bzoj1651][usaco2006feb]stallreservations专用牛棚
1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit:10Sec MemoryLimit:64MBSubmit:990 Solved:568[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N<=50,000)cows!Theyaresopi 查看详情
[bzoj1652][usaco06feb]treatsforthecows题解（区间dp）(代码片段)
[BZOJ1652][USACO06FEB]TreatsfortheCowsDescriptionFJhaspurchasedN(1<=N<=2000)yummytreatsforthecowswhogetmoneyforgivingvastamountsofmilk.FJsellsonetreatperdayandwantstomaximizethemoneyhereceivesov 查看详情
bzoj1651:[usaco2006feb]stallreservations专用牛棚
1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 942 Solved: 544[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N< 查看详情
[bzoj]1611:[usaco2008feb]meteorshower流星雨
1611:[Usaco2008Feb]MeteorShower流星雨TimeLimit:5Sec MemoryLimit:64MBSubmit:1654 Solved:707[Submit][Status][Discuss]Description去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息：一场流星雨即将袭击整个霸... 查看详情
bzoj1734:[usaco2005feb]aggressivecows愤怒的牛
1734:[Usaco2005feb]Aggressivecows愤怒的牛DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2<=N<=100,000)stalls.Thestallsarelocatedalongastraightlineatpositionsx1,...,xN(0<=xi<=1,000,000,000).Hi 查看详情
bzoj3940[usaco2015feb]censoring*
bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。题解：对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成... 查看详情
bzoj1593:[usaco2008feb]hotel旅馆
1593:[Usaco2008Feb]Hotel旅馆TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 800 Solved: 441[Submit][Status][Discuss]Description奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作 查看详情