POJ2431 Expedition 贪心
正解:贪心
解题报告:
先放个传送门鸭,题目大意可以点$Descriptions$的第二个切换成中文翻译
然后为了方便表述,这里强行改一下题意(问题是一样的只是表述不一样辣,,,
就是说现在在高速公路上行驶,初始有$K$的油量,每走一公里要消耗一单位的油,然后路上有$N$个加油站,离终点的距离分别为$A_i$,每次经过一个加油站可以选择加或者不加,加就能加$B_i$的油量,然后要求路上不能存在没油的情况,问最少要加几次油
然后就考虑可以理解成,每经过一个加油站,就相当于有加油的权利,所以把它加入堆中,当没油的时候从堆中找出油量$max$就好
然后就做完辣!这题还是比较水的$QAQ$
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define il inline #define gc getchar() #define t(i) edge[i].to #define mp make_pair #define ri register int #define rb register bool #define rc register char #define lb(x) lower_bound(st+1,st+st_cnt,x)-st #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) #define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=1e4+10; int K,f,n,nw=1,as; struct nod{int a,b;}node[N]; priority_queue<int>Q; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch<'0' || ch>'9'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il bool cmp(nod gd,nod gs){return gd.a<gs.a;} int main() { freopen("2431.in","r",stdin);freopen("2431.out","w",stdout); n=read();rp(i,1,n)node[i]=(nod){read(),read()};f=read();K=read();rp(i,1,n)node[i].a=f-node[i].a;sort(node+1,node+1+n,cmp); node[++n].a=f;node[n].b=0; rp(i,1,n) { while(K<node[i].a && !Q.empty())K+=Q.top(),Q.pop(),++as; if(K>=node[i].a)Q.push(node[i].b); } if(K>=f)printf("%d\n",as);else printf("-1\n"); return 0; }