Home PAT 1033 To Fill or Not to Fill
Post
Cancel

PAT 1033 To Fill or Not to Fill

Link

让我滞留了三个小时的题 —— 是我太菜了, 对不起 😓

『 🫧 』: 可它才 25 分哪… 考试不也就 3 个小时吗?

我就卡在了一个细节上: 在可及范围内寻找下一个加油站时, 一旦遇到低于当前加油站价格的加油站, 就先到那里去, 而不是找价格最低的那个! 如果在可及范围内一直都没有找到低于当前价格的, 才是取价格最低的那个 (但是仍然比当前价格高).

这是因为, 如果不在第一个低于当前价格的加油站停下来, 就会用当前价格买到 (可及范围内) 最低价格加油站的油; 而停下来的话, 就只需要用当前价格买到第一个低于当前价格的加油站的油, 然后用第一个低于当前价格的加油站的油价买到下一个加油站的油.

I will elaborate the process in the following way:

妥妥的贪心算法. 整体的思路是:

  • 如果在 dis=0 的地方没有加油站, 则哪里都去不了, 因为初始时油箱是空的;
  • n 个加油站按照到出发点的距离从小到大排序. 如果距离相等, 就按照价格从低到高排序;
  • 如果有加油站刚好在目的地, 就去掉这些加油站, 缩小 n 的值. 因为没必要在终点加油;
  • 如果目的地就在出发点 (d==0), 就不用买油了, 直接输出并 return 0;
  • cLeft 表示油箱中剩余的空间, 即油箱还可以装 cLeft 单位的油;
  • cmax 表示油箱的总容量, 即油箱总共可装 cmax 单位的油;
  • davg 是每一单位油可以行驶的距离;
  • 初始时, 所在的加油站是 dis==0 处的加油站, 编号是 1, 因此 cur=1; 此时还没有加油, 因此油箱是空的, cLeft==cmax;
  • cur+1 开始向后寻找 (因此需要单独考虑 cur==n 的情况, 这个下面会说), 一旦找到了一个低于当前价格的加油站, 就 break, 否则在可及范围内找价格最低的那个加油站. 其中, 可及范围是指油箱中所有的油能够行驶的距离, 即 cmax*davg;
  • 假设找到的下一个加油站的编号是 index, 其油价是 minv:
    • minv 小于当前价格, 就只需要保证油箱中的油足够到 index 号加油站即可. 如果油箱中的油不足, 就先在当前加油站把油补足 (补到刚好够到 index 站); 否则, 就直接去 index 号加油站;
    • minv 大于当前价格: 如果我现在把油箱加满, 足够我到目的地去, 我为什么还要中途停留呢 (毕竟价格都比现在高啊). 因此, 这种情况下就在当前站加足刚好能去目的地的油 (如果油箱中剩余的油够了就不用加, 就算最后到了目的地有剩余那也没办法-_-), 直接前往目的地; 否则, 就选择可及范围内价格最低的那个加油站, 并去那个加油站;
  • 对于 cur==n 的情况, 也就是当前处于最后一个加油站: 如果目的地仍然在可及范围之外, 那就说明到不了; 否则, 只能在当前站加油, 并去目的地了;
  • 不能到达目的地的判断情况: 当前站的下一站在当前站的可及范围之外.

I think I have made it clear! And I think I have considered all the situations. If not, send an email to inform me!

AC 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
double cmax,d,davg,cLeft,maxd;
int n,cur;
double ans=0.0;
struct node{
    double price,dis;
    bool operator<(node x)const{
        if(dis!=x.dis) return dis<x.dis;
        return price<x.price;
    }
}station[510];
int main() {
    scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&station[i].price,&station[i].dis);
    sort(station+1,station+1+n);
    //如果有加油站刚好在目的地
    int j=n;
    while(station[j].dis==d&&j>=1) j--;
    n=j;
    if(station[1].dis>0||n<1){
        printf("The maximum travel distance = 0.00\n");
        return 0;
    }
    if(d==0){
        printf("0.00\n");
        return 0;
    }
    cLeft=cmax,cur=1;
    maxd=cmax*davg;
    while(cur<=n){
        if(cur==n){
            if(maxd<d-station[cur].dis){
                printf("The maximum travel distance = %.2lf\n",station[cur].dis+maxd);
                return 0;
            }else{
                double units=(d-station[cur].dis)/davg;
                if(units>cmax-cLeft)
                    ans+=station[cur].price*(units-(cmax-cLeft));
                break;
            }
        }
        if(station[cur+1].dis>maxd+station[cur].dis){
            printf("The maximum travel distance = %.2lf\n",station[cur].dis+maxd);
            return 0;
        }
        double minv=99999999;
        int index=cur;
        for(int i=cur+1;i<=n;++i){
            if(station[i].dis>maxd+station[cur].dis) break;
            if(station[i].price<minv){
                minv=station[i].price;
                index=i;
                if(minv<station[cur].price) break;
            }
        }
        if(minv<=station[cur].price){
            double units=(station[index].dis-station[cur].dis)/davg;
            if(cmax-cLeft>=units){ //目前的油还够用就不在这里加油,直接去index站
                cLeft+=units;
            }else{//充到刚好够到index站的油
                ans+=station[cur].price*(units-(cmax-cLeft));
                cLeft=cmax;//到index站时油全部用完
            }
        }else{//可及范围内的加油站的价格都比当前高
            if(maxd>=d-station[cur].dis){//如果从当前站可以直接到目的地,就直接去目的地
                double units=(d-station[cur].dis)/davg;
                if(units>cmax-cLeft)//当前剩下的油不够用
                    ans+=station[cur].price*(units-(cmax-cLeft));//加上油使得刚好能在到达目的地时用完
                break;
            }
            //去可及范围内价格最低的那个加油站index
            ans+=station[cur].price*cLeft;//把油箱加满
            cLeft=(station[index].dis-station[cur].dis)/davg;
        }
        cur=index;
    }
    printf("%.2lf\n",ans);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.