文章

1

粉丝

35

获赞

2

访问

1.2k

头像
基于大佬代码的更加清晰的版本(高强度注释)
P1347 浙江大学机试题
发布于2023年7月19日 21:10
阅读数 1.2k

/*
我们假设会经过所有的加油站
我们可以假装持有价格高得油,一旦遇到价格低的就进行替换
在经过加油站的时候,我们补充该加油站的油(注意是假设补充,具体是否补充要看之后有没有遇见更加便宜的油)
比如,我们的油箱在遇到价值4快的加油站时,还剩下2块钱的油和5块钱的油,这说明之前假装补充的5块钱的油
是可以被四块钱的油所替代,因此
我们就可以补充油
注意计算cost的时候要以实际花费的油为准,而不是在补充油的时候进行计算
*/

#include<bits/stdc++.h>
using namespace std;

// double判断相等需要用一个接近无穷小
#define eps 1e-8

//加油站结构体
struct Station{
    double price, distance;
}s[200];

bool cmp(Station s1, Station s2){
    return s1.distance < s2.distance;
}

int main(){
    double cmax, d, davg;
    int n;
    while (scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n) != EOF){
        // 从1开始,较为清晰
        for (int i = 1; i <= n; i++){
            scanf("%lf%lf", &s[i].price, &s[i].distance);
        }
        //终点看作特殊的加油站
        s[n+1].distance = d;
        s[n+1].price = 0;
        //注意这里的上下界
        sort(s+1, s+1+n+1, cmp);
        //双端队列,一方面弹出最低价格的油作为消耗;另一方面弹出最高价格的油作为替换
        deque<pair<double, double>> d;
        doub...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发