第十二章贪心 7 AcWing 1517. 是否加满油

我不是女神ヾ 2024-03-31 13:55 74阅读 0赞

## 第十二章 贪心 7 AcWing 1517. 是否加满油 ##

### 原题链接 ###

[AcWing 1517. 是否加满油][AcWing 1517.]

### 算法标签 ###

贪心

### 思路 ###

思路见代码

### 代码 ###

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define xx first
    #define yy second
    #define ump unordered_map
    #define us unordered_set
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N=505, inf=0x3f3f3f3f3f3f3f3f, mod=1e9+7;
    const double Exp=1e-8;
    //int t, n, m, cnt, ans; 
    struct St{
        double p, d;
        bool operator<(const St &s){
            return d<s.d;
        }
    }s[N];
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    // 	int cm=rd(), d=rd(), da=rd(), n=rd();
        int cm, d, da, n;
        scanf("%lld %lld %lld %lld", &cm, &d, &da, &n);
    	rep(i, 0, n){
    	    scanf("%lf %lf", &s[i].p, &s[i].d);
    	}
    	s[n]={0, (double)d};
    	sort(s, s+n+1);
    	// 起点没有加油站
    	if(s[0].d){
    	    printf("The maximum travel distance = 0.00");
    	    return 0;
    	}
    	// oil为当前油箱中的油 初始时还未决策 故油量为0
    	double res=0, oil=0;
    	for(int i=0; i<n; ){
    	    int k=-1;
    	    // 枚举当前油量能够走到的所有加油站 初始在0号点最远可达c_max * d_avg(油箱满)
    	    for(int j=i+1; j<=n&&s[j].d-s[i].d<=cm*da; ++j){
    	    	// 找到第一个比起点价格小的
    	        if(s[j].p<s[i].p){
    	            k=j;
    	            break;
    	        }else if(k==-1||s[j].p<s[k].p){// 或者找一个不比起点小但比这一段最小的
    	            k=j;
    	        }
    	    }
    	    // 这一段之间没有加油站
    	    if(k==-1){
    	        printf("The maximum travel distance = %.2lf", s[i].d+(double)cm*da);
    	        return 0;
    	    }
    	    // 存在比当前加油站更便宜的加油站A 只补充合适的油
    	    if(s[k].p<=s[i].p){
    	    	// (s[k].d-s[i].d)/da
    	    	// 走到A站的总耗油量
    	    	// (s[k].d-s[i].d)/da-oil
    	    	// 总耗油量减去当前油箱中的油量为需要补充的油量
    	    	// ((s[k].d-s[i].d)/da-oil)*s[i].p
    	    	// 需要补充的油量的花费
    	        res+=((s[k].d-s[i].d)/da-oil)*s[i].p;
    	        // 此时剩余的油量只能够正好走到下一站
    	        i=k;
    	        // 走到下一站后油量刚好耗尽
    	        oil=0;
    	    }else{ /* 可达范围内存在加油站 但价格都比当前加油站的价格更高
            此时最优选择是在当前车站把油箱填满 到了范围内最低价格的加油站再做下一步选择*/
            // 花费为: 走到[花费最优的加油站]的距离 * 油价
    	        res+=(cm-oil)*s[i].p;
    	        // 走到那里时油量为:满油减去耗费的油  
    	        oil=cm-(s[k].d-s[i].d)/da;
    	        i=k;
    	    }
    	    
    	}
    	printf("%.2lf", res);
    	return 0;
    }

### 参考文献 ###

[AcWing 1517. 是否加满油（PAT甲级辅导课）y总视频讲解][AcWing 1517. _PAT_y]  
[AcWing 1517. 是否加满油—注释版][AcWing 1517. 1]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1517.]: https://www.acwing.com/problem/content/1519/
[AcWing 1517. _PAT_y]: https://www.acwing.com/video/1297/
[AcWing 1517. 1]: https://www.acwing.com/solution/content/86971/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3883481510014656ba8021b57528a0bf.png