关键词：
bzoj2590[Usaco2012 Feb]Cow Coupons
题意：
市场上有N头奶牛，第i头奶牛价格为Pi。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci，每头奶牛只能使用一次优惠券。FJ想知道花不超过M的钱最多可以买多少奶牛。n≤50000，m≤10^14。
题解：
先按ci升序排序，把前k头买下来（如果可以的话）接着把剩下的牛按pi升序排序：如果当前奶牛优惠价与原价差值比k头奶牛中最大的一头大，则花那一头优惠价与原价差值把优惠券“赎”回来，并用优惠价买当前奶牛；否则直接以原价买当前奶牛。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 50010 7 #define INF 0x3fffffff 8 #define ll long long 9 using namespace std; 10 11 inline ll read(){ 12 char ch=getchar(); ll f=1,x=0; 13 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} 14 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); 15 return f*x; 16 } 17 struct nd{int p,c;}nds[maxn]; int n,k; ll m,sum; priority_queue<int,vector<int>,greater<int> >q; 18 bool cmp1(nd a,nd b){return a.c<b.c;} 19 bool cmp2(nd a,nd b){return a.p<b.p;} 20 int main(){ 21 n=read(); k=read(); m=read(); inc(i,1,n)nds[i].p=read(),nds[i].c=read(); sort(nds+1,nds+1+n,cmp1); 22 inc(i,1,k){ 23 sum+=nds[i].c; if(sum>m){printf("%d",i-1); goto end;} 24 if(i==n){printf("%d",n); goto end;} q.push(nds[i].p-nds[i].c); 25 } 26 sort(nds+1+k,nds+n+1,cmp2); 27 inc(i,k+1,n){ 28 int t=q.empty()?INF:q.top(); 29 if(nds[i].p-nds[i].c>t){sum+=t; q.pop(); sum+=nds[i].c; q.push(nds[i].p-nds[i].c);}else sum+=nds[i].p; 30 if(sum>m){printf("%d",i-1); goto end;} if(i==n){printf("%d",n); goto end;} 31 } 32 end: return 0; 33 }
20161031
bzoj1651:[usaco2006feb]stallreservations专用牛棚
二次联通门: BZOJ1651:[Usaco2006Feb]StallReservations专用牛棚 权限题放题面DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA.. 查看详情
[bzoj2591][usaco2012feb]nearbycows
2591:[Usaco2012Feb]NearbyCowsTimeLimit:4Sec MemoryLimit:128MBSubmit:149 Solved:89[Submit][Status][Discuss]Description FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfi 查看详情
[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 查看详情
bzoj3942:[usaco2015feb]censoring
3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBSubmit: 404 Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情
bzoj3940[usaco2015feb]censoring
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情
[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 查看详情
[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奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作 查看详情
bzoj1593[usaco2008feb]hotel旅馆
1593:[Usaco2008Feb]Hotel旅馆TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 807 Solved: 447[Submit][Status][Discuss]Description奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作 查看详情
bzoj1676:[usaco2005feb]feedaccounting饲料计算
DescriptionFarmerJohnistryingtofigureoutwhenhislastshipmentoffeedarrived.Startingwithanemptygrainbin,heorderedandreceivedF1(1<=F1<=1,000,000)kilogramsoffeed.Regrettably,heisnotcertainexactlywhen 查看详情
bzoj3940:[usaco2015feb]censoring--ac自动机
3940:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBDescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterial 查看详情
bzoj1592[usaco2008feb]makingthegrade路面修整
1592:[Usaco2008Feb]MakingtheGrade路面修整TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 743 Solved: 514[Submit][Status][Discuss]DescriptionFJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的 查看详情