比赛 |
贪心题目练习 |
评测结果 |
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;
}