首页 > 代码库 > 洛谷1016 旅行家的预算
洛谷1016 旅行家的预算
题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N(N可以为零),油站i离出发点的距离Di、每升汽油价格Pi(i=1,2,…,N)。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
输入输出格式
输入格式:
第一行,D1,C,D2,P,N。
接下来有N行。
第i+1行,两个数字,油站i离出发点的距离Di和每升汽油价格Pi。
输出格式:
所需最小费用,计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
输入输出样例
输入样例#1:
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出样例#1:
26.95
思路
寻找当前油量能到达的最便宜的加油站,如果找到了,那就开过去加油。如果找不到, 那就寻找最近的比本站便宜的站点,找到的话就加油刚好开过去,找不到的话就寻找次优站点,充满油开过去,如果找不到任何站点,那就输出No Solution
#include<cstdio> #include<cmath> #include<algorithm> #define precision 0.0001 #define maxn 1000 using namespace std; struct tnode{double d,p;}a[maxn+10]; double d1,c,d2,p; int n; bool cmp(tnode xx,tnode yy) { return xx.d<yy.d; } int main() { int i,j,k; double s,ans,x,y; scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n); a[1].d=0,a[1].p=p; a[2].d=d1,a[2].p=0; for(n+=2,i=3;i<=n;i++)scanf("%lf%lf",&a[i].d,&a[i].p); sort(a+1,a+n+1,cmp); k=1,ans=x=0,s=c*d2; while(k<=n) { if(a[k+1].d-a[k].d>s){printf("No Solution\n");return 0;} for(j=k+1;a[j].d-a[k].d<=s && j<=n;j++) if(a[j].p<=a[k].p) { y=(a[j].d-a[k].d)/d2; if(x<y)ans+=a[k].p*(y-x),x=0; else x-=y; k=j; break; } if(fabs(a[k].d-d1)<=precision) { printf("%.2lf\n",ans); return 0; } if(j!=k) { ans+=a[k].p*(c-x); x=c-(a[k+1].d-a[k].d)/d2; k++; } } return 0; }
洛谷1016 旅行家的预算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。