[NOIP1999 提高组] 旅行家的预算
2024-10-21 13:41:50
洛咕
题意:一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 \(D_1\)、汽车油箱的容量 \(C\)(以升为单位)、每升汽油能行驶的距离 \(D_2\)、出发点每升汽油价格\(P\)和沿途油站数 \(N\)(\(N\) 可以为零),油站 \(i\) 离出发点的距离 \(D_i\)、每升汽油价格 \(P_i\)(\(i=1,2,…,N\))。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出 No Solution
。
分析:贪心策略。从当前加油站出发,如果加油能到达一个油价比当前加油站低的加油站,那当前加油就只要保证刚好能够到达那个加油站即可(贪心策略一)。如果在当前加油站即使加满油也无法到达一个油价比当前加油站低的加油站,那么就加满油,下一个到达能到达的加油站里面油价最低的(贪心策略二)。如果加满油无法到达任何一个加油站就是无法到达目的地。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int mod=100000000;
const int N=1e5+5;
const int M=5e6+5;
double dis[10],pri[10];
int main(){
double d1,c,d2,p;int n;
cin>>d1>>c>>d2>>p>>n;
for(int i=1;i<=n;++i){
cin>>dis[i]>>pri[i];
}
dis[0]=0;pri[0]=p;//起点也看做一个加油站
double maxn=c*d2; //加满油最多能走的路程
int now_sta=0;double now_dis=0,ans=0,now_c=0;
//now_sta当前到达的加油站,now_dis当前走过的距离,now_c当前剩余油量能走的路程
while(1){
now_dis=dis[now_sta];
int bj=0,j=-1;
for(int i=now_sta+1;i<=n&&dis[i]-now_dis<=maxn;i++){
if(pri[i]<pri[now_sta]){//贪心策略一
ans+=((dis[i]-now_dis-now_c)/d2)*pri[now_sta];
now_c=0;
now_sta=i;
bj=1;
break;
}
else if(j==-1||pri[i]<pri[j])j=i;//贪心策略二寻找价格最低加油站
}
if(bj)continue;
if(d1-dis[now_sta]<=maxn){//已经可以到达目的地
ans+=((d1-dis[now_sta]-now_c)/d2)*pri[now_sta];
printf("%.2lf\n",ans);
break;
}
if(j==-1){
cout<<"No Solution";
break;
}
else{//贪心策略二更新状态
ans+=c*pri[now_sta];
now_c+=(maxn-dis[j]+now_dis);
now_sta=j;
continue;
}
}
return 0;
}
最新文章
- 编译原理-词法分析05-正则表达式到DFA-01
- 第66课 C++中的类型识别
- Tomcat日志输出在linux和windows差异
- 使用clssneme改变图片或样式
- PAT乙级 1005. 继续(3n+1)猜想 (25)
- linux 文件系统(inode和block)
- (POJ 3694) Network 求桥个数
- Python读写文件需要注意的地方 2015-03-31 23:19 69人阅读 评论(0) 收藏
- img 中的src的应用
- ora-04031
- 【读书笔记】【深入理解ES6】#9-JavaScript中的类
- python 将验证码保存到本地 读取 写入
- Python面向对象篇(2)-继承
- 【转载】ASP.NET Core Web 支付功能接入 微信-扫码支付篇
- HTTP协议是无状态的
- 在OAF页面中集成ECharts以及highcharts用于显示图表
- hive最全学习线路和实践练习
- 寒假作业pta2
- NoSQL(not only struts query language)的简单介绍
- 无法启动程序,因为计算机丢失D3DCOMPILER_47.dll 的解决方法