题解 P2209 【[USACO13OPEN]燃油经济性Fuel Economy】

xuxinyu · 2017-10-01 19:27:33 · 题解

上次的忘了粘代码，管理员可以覆盖掉上一篇吗

来篇C++

首先，我们可以特判掉不能到达的情况，这样可以减小代码复杂度

不能到达的情况有三：

1、第一个加油站到起点的距离>初始油量

2、终点到最后一个加油站的距离>油箱容量

3、途中存在相邻加油站的距离>油箱容量

前提是你排好序了

为了避免代码中进行到终点的特判，可以在终点增加一个价格为0的加油站

接下来，我们需要维护当前在哪个加油站，当前剩余油量，接下来去哪个加油站

然后贪心

假设当前在now加油站

1、假设在能跑到的范围内，第一个价格比他便宜的加油站to，就在当前加油站加油，加到恰好能跑到to

2、在能跑到的范围内，没有价格比他便宜的加油站，就在now加满油，跑到能跑到的范围内，价格最便宜的加油站

注意，在1中不是跑到范围内最便宜的加油站，而是只要遇到一个比now便宜，就跑过去

跑到最便宜的只能拿40分

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int N,G,B,D;
void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
struct node
{
    int d,p;
}e[50005];
int dis[50005],price[50005];
int findmin(int s,int lim)
{
    int now=s+1,to=50003;
    while(now<=N)
    {
        if(dis[now]-dis[s]>lim) return to;
        if(price[now]<price[s]) return now;
        if(price[now]<price[to]) to=now;
        now++;
    }
}
bool cmp(node a,node b)
{
    return a.d<b.d;
}
int main()
{
    read(N);read(G);read(B);read(D);
    for(int i=1;i<=N;i++) read(e[i].d),read(e[i].p);
    sort(e+1,e+N+1,cmp);
    for(int i=1;i<=N;i++) 
    {
        dis[i]=e[i].d; price[i]=e[i].p;
        if(dis[i]-dis[i-1]>G) { printf("-1"); return 0; }
    }
    if(dis[1]>B || D-dis[N]>G) { printf("-1"); return 0; }
    price[50003]=2e9;
    int now=0,to;
    to=findmin(now,B);
    if(now>N) { printf("0"); return 0; }
    now=to;
    int nowB=B-dis[to];
    LL ans=0;
    if(dis[N]==D) price[N]=0;
    else
    {
        N++; dis[N]=D; price[N]=0;
    }
    while(now<N)
    {
        to=findmin(now,G);
        if(price[to]>price[now]) 
        {
            ans+=1ll*(G-nowB)*price[now];
            nowB=G-dis[to]+dis[now];
        }
        else
        {
            ans+=1ll*(dis[to]-dis[now]-nowB)*price[now];
            nowB=0;
        }
        now=to;
    }
    printf("%lld",ans);
}