此题是一道经典的贪心题(NOIP1999)
题目描述:
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是 空的）。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位）．每升汽油能行 驶的距离 D2、出发点每升汽油价格 P 和沿途油站数 N（N 可以为零），油站 i 离出发点的 距离 Di、每升汽油价格 Pi（ i＝l，2，...N）。计算结果四舍五入至小数点后两位。如果 无法到达目的地，则输出“No Solution”。
input:
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
out:
26.95
思路:
先判断无解的情况:在当前加油站加满油都到不了下一个加油站
接下来,遍历加油站,找到比当前加油站更便宜的第一个加油站,如果没有,则油加满,先判断时候能直接跑到终点,跑到范围内,如果跑不到,则跑到最便宜的加油站,执行上一步骤;
```cpp
#include
#include
using namespace std;
double d1,c,d2,Max,oil,cost;
int n,now_i=1;
struct node{
double di,pi;
}a[100005];
bool cmp(node x,node y){
return (x.di } int main(){ scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&a[1].pi,&n); for(int i=2;i<=n+1;i++){ scanf("%lf %lf",&a[i].di,&a[i].pi); } a[n+2].di=d1; Max=c*d2; sort(a+2,a+2+n,cmp); for(int i=2;i<=n+2;i++){ if(a[i].di-a[i-1].di>Max){ printf("No Solution"); return 0; } } while(1){ bool flag=0; int next,k; double minn=10000; for(int i=1+now_i;a[i].di-a[now_i].di<=Max&&i<=n+1;i++){ if(a[i].pi<=a[now_i].pi&&!flag){ next=i; cost+=((a[i].di-a[now_i].di)/d2-oil)*a[now_i].pi; flag=1; oil=0; break; } if(!flag&&a[i].pi minn=a[i].pi; k=i; } } if(!flag){ if(d1-a[now_i].di<=Max){ cost+=((d1-a[now_i].di)/d2-oil)*a[now_i].pi; break; } else{ next=k; cost+=a[now_i].pi*(c-oil); oil=c-(a[k].di-a[now_i].di)/d2; } } now_i=next; } printf("%.2lf",cost); return 0; } ```
