(重要！) 贪心
思路
首先将各加油站按照距离进行排序，如果没有距离为0的加油站，则直接输出The maximum travel distance = 0.00；若有则进行下面的判断。 对于每个加油站加多少最为合适？用贪心策略。 设当前我们站在加油站A。 1） 如果在A能到达的最大范围内（即假设在A加满油），有加油站的油价比当前站A的油价低：设距离A最近的且比A小的加油站为B，则加到能恰好到B加油站距离的油量就是一个局部最优策略。 2） 如果在最大的范围内没有加油站油价比当前低：则在A加满（加满是因为，无论在范围之外有多小多小的油价，即使加满也无法到达，还需要中间一个加油站中转，但既然当前油价最低，能加满就加满，之后油钱高的就可以少加点）。 不断的循环这个过程，在正常情况下到达目的地就终止循环，根据上述策略，可以将目的地也看做加油站，其距离设置为相应距离，油钱为0，这样其油钱一定比所有的加油站油钱都要低，在最后一定会选择目的地作为下一到达加油站。但是要注意，有可能当前加油站最近的一个加油站超过了车能行驶的最大距离（即最大的油量*每升行驶路程），则无法到达目的地，最长距离就是当前加油站的位置+车能行驶的最大距离。
tips
先判断如果第一个加油站不在起点，则直接输出无法到达。因为循环中的每次判断都是站在一个加油站的立场上的，如果0处没有加油站，循环内检查不出，所以要提前单独判断。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 502
struct station {
double begin;
double price;
};
double cmax;//油箱最大内存
double dissum;//总路程
double davg;//每单位油可以跑的公里数
int n;
vector<station>sta;
bool cmp(station a, station b) {
return a.begin < b.begin;
}
int main() {
scanf("%lf%lf%lf%d", &cmax, &dissum, &davg, &n);
int i, j;
station tempsta;
for (i = 0;i < n;i++) {
scanf("%lf%lf", &tempsta.price, &tempsta.begin);
sta.push_back(tempsta);
}
tempsta.price = 0;
tempsta.begin = dissum;
sta.push_back(tempsta);
sort(sta.begin(), sta.end(), cmp);
double priceans = 0;
double nowgas = 0;
double fulldis = cmax * davg;//加满油可以走的公里数
if (sta[0].begin != 0) {
printf("The maximum travel distance = 0.00");
return 0;
}
for (i = 0;i < n;i++) {
j = i + 1;
int flag = 0;
double iffulldis = sta[i].begin + fulldis;
while (sta[j].begin < iffulldis) {
if (sta[j].price < sta[i].price) {
flag = 1;
break;
}
else j++;
}
if (flag == 0) {//在i处加满油
priceans += (cmax - nowgas) * sta[i].price;
nowgas = cmax;
}
else {//在i处只加到够跑到j
if (nowgas < (sta[j].begin-sta[i].begin)/davg) {//i没加之前不能跑到j
double need = (sta[j].begin - sta[i].begin) / davg - nowgas;
priceans += need * sta[i].price;
nowgas = nowgas + need;
}
}
nowgas -= (sta[i + 1].begin - sta[i].begin) / davg;
if (nowgas < 0) {
double maxdis = sta[i].begin + fulldis;
printf("The maximum travel distance = %.2lf", maxdis);
return 0;
}
}
printf("%.2lf", priceans);
return 0;
}
