p1016旅行者的题解

h1lpen · 2024-11-23 22:42:56 · 题解

纪念蒟蒻的第一次切绿题没有看题解独自ac且一次过

其实也看了一下

题目链接[(https://www.luogu.com.cn/probleP1016)]

不难发现，只需要进行两种决策，一种是到达更便宜的油站，实在不行就奢侈一把，用98的好油，实际上都是跑那么点距离

从最简单的决策思考，一种跳出循环的方式即是找到更便宜的油站，撞狗屎运了，另一种便是去最远的地方去接点好油

q:那么如何跑到最远呢？

a:很简单，奢侈一把装满油即可 代码实现如下

#include<bits/stdc++.h>
using namespace std;
struct add{
    double qian;
    double di;
}a[10];
double ans=0;
double d,c,d2,p;
int n;
double now;//表当前油箱剩余的量
/*bool cmp(add x,add y){
    return x.qian<y.qian;
}抽象排序别看了
*/
int main(){
    cin>>d>>c>>d2>>p>>n;
    a[n+1].di=d;
    a[0].qian=p;
    for(int i=1;i<=n;i++){
        cin>>a[i].di>>a[i].qian;
        if(a[i].di-a[i-1].di>c*d2){//吃饱了跑不过去就躺地上说出那句话即可
            cout<<"No Solution"<<"\n";
            return 0;
        }
    }
    int j=0;
    for(int i=0;i<=n+1;i=j){
        for(j=i+1;j<=n+1;j++){//有且仅有两种跳出的方式
            if(a[j].di-a[i].di>c*d2){
                j--;
                break;
            }
            if(a[j].qian<a[i].qian){
                break;
            }
        }
        if(a[j].qian<a[i].qian){//有小的就跑去
            ans+=((a[j].di-a[i].di)/d2-now)*a[i].qian;
        }
        else {
            ans+=(c-now)*a[i].qian;
            now=c-(a[j].di-a[i].di)/d2;
        }//这里是实在没有小的了，能去的最远的距离，为什么这样写可以呢？
    }
    printf("%.2f\n",ans);//ans:因为每一步都是当前最优解
    return 0;
}

对了，感谢大佬@swkyccbb的思路，虽然您早已不在luogu但感谢您的思路

good bye