题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。
给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N(N可以为零),油站i离出发点的距离Di、每升汽油价格Pi(i=1,2,…,Ni=1,2,…,N)。
计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
输入格式
第一行,D1,C,D2,P,N。
接下来有N行。
第i+1行,两个数字,油站i离出发点的距离Di和每升汽油价格Pi。
输出格式
所需最小费用,计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
输入输出样例
输入
275.6 | 11.9 | 27.4 | 2.8 | 2 |
---|---|---|---|---|
102.0 | 2.9 | |||
220.0 | 2.2 |
输出
26.95 |
---|
思路
这道题我们可以用模拟加贪心的方法来解决
非AC代码,在打代码时要有规律,思路要清晰
#include<bits/stdc++.h>
using namespace std;
struct node{
int wz,jg;
}a[10001];
int main(){
double d1,c,d2,p,n;
cin>>d1>>c>>d2>>p>>n;
for(int i=1;i<=n;i++){
cin>>a[i].wz>>a[i].jg;
}
double tot=0;
double rest=d1;
double maxx=c*d2;
a[0].jg=p;
a[0].wz=0;
double vis=0;
double zdj;
int jlu;
for(int i=1;i<=n;i++){
if(a[i].wz>a[i-1].wz+maxx){
cout<<"No Solution"<<endl;
return 0;
}
else{
tot+=(a[i].wz-a[i-1].wz)*a[i-1].jg/d2;
rest=c-a[i-1].wz;
if(a[i].jg>a[i-1].jg){
int now=i-1;
while(a[i].wz-a[now].wz<=maxx){
zdj=min(a[i].jg,a[now].jg);
if(zdj==a[i].jg){
jlu=i;
}
i++;
if(i>n){
break;
}
}
if(zdj==a[now].jg){
vis=c-vis-(a[i].wz-a[i-1].wz)/d2;
if(rest>=vis*d2){
tot+=vis*a[now].jg;
}
else{
vis=rest/d2;
tot+=vis*a[now].jg;
printf("%.2lf\n",tot);
return 0;
}
}
else{
tot+=a[now].jg*(a[jlu].wz-a[now+1].wz);
vis=0;
rest=c-a[jlu].wz;
}
}
}
}
printf("%.2lf\n",tot);
return 0;
}
AC代码,思路清晰
#include <bits/stdc++.h>
double D0,C,D,cost,left;
struct node
{
double d,p;
}s[8];
int n;
bool cmp(node a,node b){return a.d<b.d;}
int main()
{
scanf("%lf%lf%lf%lf%d",&D0,&C,&D,&s[0].p,&n);
s[n+1].d=D0;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&s[i].d,&s[i].p);
if(s[i].d-s[i-1].d>C*D)//中间有一段路加满油也到不了下个节点
{
printf("No Solution");
return 0;
}
}
std::sort(s+1,s+1+n,cmp);
for(int i=0;i<=n+1;)
{
int j,k;
for(j=k=i+1;j<=n;j++)//若直达终点,j++后j为n+1而不是n+2
{
k=s[j].p<=s[k].p?j:k;//范围内最小花费
if(s[j].p<=s[i].p||s[j+1].d-s[i].d>C*D)break;//找到下一个比当前节点便宜的节点或者到不了下个节点
}
if(s[j].p>s[i].p)//策略2
{
cost+=(C-left)*s[i].p,left=C-(s[k].d-s[i].d)/D;
i=k;
}
else
cost+=s[i].p*((s[j].d-s[i].d)/D-left),i=j,left=0;//策略1
}
printf("%.2lf",cost);
return 0;
}
原文链接: https://www.cnblogs.com/wozuishuaiwozuiniu6/p/13151295.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/356491
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!