POJ2431 Expedition 贪心

时间：2023-12-13 08:17:20

正解:贪心

解题报告:

先放个传送门鸭,题目大意可以点$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+;

int K,f,n,nw=,as;

struct nod{int a,b;}node[N];

priority_queue<int>Q;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch<'' || ch>''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),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,,n)node[i]=(nod){read(),read()};f=read();K=read();rp(i,,n)node[i].a=f-node[i].a;sort(node+,node++n,cmp);

    node[++n].a=f;node[n].b=;

    rp(i,,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 ;

}

这儿是代码鸭!

相关文章