题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805458722734080

思路

这题有点难度的，也可能是因为这两天在准备班会和简历的关系吧，有一段时间没写代码了，导致这题写起来比较吃力，不过还是把算法笔记上的代码给看懂了。
画一下思维导图

*A1033 To Fill or Not to Fill - 图1

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 510;//加油站数量
  6. const int INF = 1000000000;
  7. struct station{
  8.     double price, dis;
  9. }st[maxn];
  10. bool cmp(station a, station b){
  11.     return a.dis < b.dis;
  12. }
  13. int main(){
  14.     int n;
  15.     double Cmax, D, Davg;
  16.     scanf("%lf%lf%lf%d",&Cmax, &D, &Davg, &n);
  17.     for(int i = 0; i < n; i++){
  18.         scanf("%lf%lf",&st[i].price,&st[i].dis);
  19.     }
  20.     st[n].price = 0;
  21.     st[n].dis = D;//放置终点
  22.     sort(st, st + n, cmp);
  23.     if(st[0].dis!=0){
  24.         printf("The maximum travel distance = 0.00\n");
  25.     } else {
  26.         int now = 0;
  27.         double ans = 0, nowTank = 0, MAX = Cmax * Davg;
  28.         while(now < n){//选下一个加油站
  29.             int k = -1;
  30.             double priceMin = INF;
  31.             for(int i = now + 1; i <= n && st[i].dis - st[now].dis <= MAX; i++){//距离在可行使范围内
  32.                 if(st[i].price < priceMin){//如果比当前油价低
  33.                     priceMin = st[i].price;
  34.                     k = i;//记录加油站
  35.                     //第一个低于当前油价的直接退出循环
  36.                     if(priceMin < st[now].price){
  37.                         break;
  38.                     }
  39.                 }
  40.             }
  41.             if(k == -1) break;//找不到结果那么退出循环
  42.             //下面计算花费
  43.             double need = (st[k].dis - st[now].dis) / Davg;
  44.             if(priceMin < st[now].price){//若低于当前油价，那么只需要加足够到达K的油
  45.                 if(nowTank < need){
  46.                     ans += (need - nowTank)*st[now].price;
  47.                     nowTank = 0;//到达下一个加油站
  48.                 } else {
  49.                     nowTank -= need;
  50.                 }
  51.             } else {//目的油站k比当前油价高，那么加满
  52.                 ans += (Cmax - nowTank) * st[now].price;//油箱剩多少油
  53.                 nowTank = Cmax - need;
  54.             }
  55.             now = k;
  56.         }
  57.         if (now == n){
  58.             printf("%.2f\n",ans);
  59.         } else {
  60.             printf("The maximum travel distance = %.2f\n",st[now].dis + MAX);//路程是当前距离加油箱内油最远行驶距离
  61.         }
  62.     }
  63.     return 0;
  64. }