题目描述 Description
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入描述 Input Description
第一行D1 C D2 P N
之后N行，每行2个数表示离出发点的距离Di和每升汽油的价格Pi
输出描述 Output Description
最消费用，保留2位小数
样例输入 Sample Input
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出 Sample Output
26.95
数据范围及提示 Data Size & Hint
N<=100
【题目大意】
开车从一个点到另一个点，行驶道路需要耗油，路上有N个加油站，问能否到达和最小花费。
【思路】
贪心
能行驶到比当前油费更少的加油站就开过去，不能则加满油。
如果在当前加满油仍行驶不到下一个加油站则no solution
【code】逼我搜题解
#include<iostream>
#include<cstdio>
using namespace std;
double D1,C,D2,P;
int N;
int now,mgood=;
double d[],p[],over[];
double ans,s;
int main() {
// scanf("%lf%lf%lf%lf%lf",&D1,&C,&D2,&P,&N);
cin>>D1>>C>>D2>>P>>N;
for(int i=; i<=N; i++) {
// scanf("%lf%lf",&d[i],&p[i]);
cin>>d[i]>>p[i];
if(d[i]-d[i-]>C*D2) {
printf("No Solution\n");
return ;
}
}
d[]=;
d[N+]=D1;
p[]=P;
p[N+]=;
while(now!=N+) {
s=;
while(s<=C*D2&&now<=N+&&mgood<=N+&&p[mgood]>=p[now]) {
mgood++;
s=s+d[mgood]-d[mgood-];
}
if(s<C*D2) {
if(over[now]>d[mgood]-d[now]) {
over[mgood]=over[now]-d[mgood]+d[now];
} else {
ans+=(d[mgood]-d[now]-over[now])/D2*p[now];
over[mgood]=;
}
} else {
ans+=(C*D2-over[now])/D2*p[now];
mgood=now+;
over[mgood]=(C*D2)-(d[mgood]-d[now]);
}
now=mgood;
}
// cout<<ans;
printf("%.2lf",ans);
return ;
}
【code2】求助 最后一个点orz
#include<iostream>
#include<cstdio>
using namespace std;
double d[],p[],over[];
int now,k,s;
double ans,D1,C,D2,P,N;
int main() {
cin>>D1>>C>>D2>>P>>N;
for(int i=; i<=N; i++) {
cin>>d[i]>>p[i];
if(d[i]-d[i-]>D2*C) {
printf("No Solution\n");
return ;
}
}
d[]=,p[]=P;
while() {
s=;
for(k=now+; k<=N; k++) {
if(p[k]<p[now]) {
s=k;
break;
}
}
if(!s) {
ans+=(D1-d[now])/D2*p[now];
break;
} else {
ans+=(d[s]-d[now])/D2*p[now];
now=s;
}
}
printf("%.2lf\n",ans);
return ;
}