比赛 贪心题目练习 评测结果 AAAW
题目名称 旅行家的预算 最终得分 75
用户昵称 梧叶已同秋雨去 运行时间 0.012 s
代码语言 C++ 内存使用 3.58 MiB
提交时间 2025-03-22 10:13:38
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
double d1,c,d2,p;int n;
double a[25],s[25],ans;
int main(){
    freopen("lyuxing.in","r",stdin);
    freopen("lyuxing.out","w",stdout);
    cin>>d1>>c>>d2>>p>>n;
    int d=0;
    a[d]=p;double f=c*d2;
    for(int i=1;i<=n;i++){
        cin>>s[i]>>a[i];
        if((s[i]-s[i-1])>f){
            cout<<"No Solution";
            return 0;
        }
    }
    s[n+1]=d1;
    while(d<=n){
        double aminn=1e16,sminn=0;int dminn=0;
        for(int i=d+1;i<=n+1;i++){ 
            if(s[i]-s[d]<=f){
                if(a[i]<a[d]){
                    aminn=a[i];
                    sminn=s[i]-s[d];
                    dminn=i;
                    break;
                }
                if(a[i]<aminn){
                    aminn=a[i];
                    sminn=s[i]-s[d];
                    dminn=i;
                }
            } 
        }
        ans+=(sminn/d2)*a[d];
        d=dminn;
    }
    if(d==n+1){
        printf("%.2lf",ans);
    }else{
        printf("No Solution");
    }
    return 0;
}