燃油经济性Fuel Economy
题目大意：FJ想要去旅行。他的车总容量为G，每行驶一个单位就消耗一个单位的油。FJ要行驶D个单位的距离。期间存在n个加油站，每个加油站有一个价格，表示在这个燃油站买一个单位的油的价格val；还有一个距离d，表示这个燃油站距离FJ起点的距离。FJ起始有B个单位的油。请输出FJ到达终点的最小花费，如果FJ无法到达终点请输出-1。
注释：$1le Gle10^6$，$1le D le 10^9$，$1le Nle 5cdot 10^4$，$0le dle D$，$1le valle 10^6$。
想法：dp了半天，什么旅行家的预算乱七八糟的... ...正解是贪心，还挺巧妙的。(先把无解的判掉，即如果两个加油站之间的距离大于D就无解了)
首先，考虑FJ在第x个加油站。如果从$d_x$开始后面的D个单位中存在的第一个加油站y使得$val_y<val_x$，那么就恰好将FJ的油加到能到y，然后到y。为什么是对的？首先如果FJ后面有2个加油站y和z使得$val_y>val_z$但$d_x < d_y < d_z$。这时，如果我们令FJ直接到达了z，如果当前油量够，那么无论是直接到达z还是先到y再到z，最后是一样的；如果当前油量不够，如果直接到z就需要在x加油站补上z到x之间的油量差，如果先到y再到z只需要在x补上y到x的油量差然后剩下的在y号加油站购买，这样显然是比直接到z更优的。
其次，如果从$d_x$开始的D个单位中的所有加油站都比$val_x$大，那么我们就直接到后面D个单位中最小的那个。证明是类似的：假设val最小的加油站是z，z和x中间有一个加油站y满足$d_x<d_y<d_z$且$val_x<val_z<val_y$。如果直接到z，需要在x补上z和x之间的油量差。如果先到达了y，那么根据我们的贪心策略，现在x补上y与x之间的油量差，剩下的z与y之间的油量差在y上补。因为$val_x<val_y$，所以这样一定是更优的。
这样我们就证明了贪心策略的正确性，证毕。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 50005
typedef long long LL;
int n,G,B,D;
struct node
{
int d,p;
}e[N];
int dis[N],price[N-2];
int dispose(int s,int lim)
{
int now=s+1,to=N;
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++;
}
return to;
}
bool cmp(node a,node b)
{
return a.d<b.d;
}
int main()
{
scanf("%d%d%d%d",&n,&G,&B,&D);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&e[i].d,&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[N-2]=2e9;
int now=0,to;
to=dispose(now,B);
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=dispose(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);
return 0;
}
小结：此题的贪心是好想且巧妙的。