比赛 贪心题目练习 评测结果 WAWW
题目名称 旅行家的预算 最终得分 25
用户昵称 二乾五 运行时间 0.013 s
代码语言 C++ 内存使用 3.64 MiB
提交时间 2025-03-22 09:29:30
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pll pair<ld,ll>
#define min1 mingasp.top().first
#define min2 mingasp.top().second

ld dis,c,dpg,gasp[15],gasd[15],maxdis,ans;
//dpg DistancePerGasoline
ll n;

priority_queue<pll,vector<pll >,greater<pll > >mingasp;
//gasp,i

int main(){
    freopen("lyuxing.in","r",stdin);
    freopen("lyuxing.out","w",stdout);
    cin>>dis>>c>>dpg>>gasp[0]>>n;
    
    mingasp.push({gasp[0],0});
    maxdis=dpg*c;
    gasd[n+1]=dis;
    gasp[n+1]=1145141919810;
    
    for(ll i=1;i<=n+1;i++){
        if(i<n+1)cin>>gasd[i]>>gasp[i];
        if(gasd[i]-gasd[min2]<=maxdis){
            ans+=(gasd[i]-gasd[i-1])/dpg*min1;
            mingasp.push({gasp[i],i});
        }else if(gasd[i]-gasd[i-1]>maxdis&&(gasd[i]-gasd[i-1]-maxdis)>=0.0001){
            cout<<"No Solution";
            return 0;
        }
        else{
            ans+=(maxdis-gasd[i]+gasd[i-1])/dpg*min1;
            mingasp.pop();
            mingasp.push({gasp[i],i});
            ans+=(gasd[i]-gasd[i-1]-maxdis+gasd[i]-gasd[i-1])/dpg*min1;
        }
    }
    printf("%.2f",round(ans*1000.0)/1000.0);
    return 0;
}