因为时间问题,我只能给出我的思路
by whwh @ 2019-06-07 08:05:25
变量的作用:
1.q[],d1,d2,c,p储存数据,ans储存钱数
2.c1记录在第i个加油站时得油量
3.w记录第i加油站在[i,w)中的加油费最小
4.u记录第i个加油站到下一个加油站所需的油量(也可不用,直接写)
5.max2记录在第i个时,c和(q[n+1].d-q[i].d)/d2(从第i个加油站所需的油量)中更小的一个,max2取后者是因为如果大于此值就会有油剩余,自然ans不是最小值
6.最最重要的一个,book[]记录哪一些加油站可以忽略掉
7.(q[x].d-q[y].d)/d2(x>y) 表示的是从第x个加油站到第y个加油站所需的油
by whwh @ 2019-06-07 08:05:32
```
#include<cstdio>
struct note{
double d,p;
}q[10];
double min1(double x,double y){
if(x>y) return y;
return x;
}
bool book[10];
int main(){
double d1,c,d2,p,c1=0,ans=0;
int n,w;
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n);
for(int i=1;i<=n;++i) scanf("%lf%lf",&q[i].d,&q[i].p);
//这一行初始化,为后面计算ans,u,w,c1,max2做准备,自行理解一下
q[0].p=p;q[0].d=0;q[n+1].d=d1;q[n+1].p=0;
for(int i=0;i<n;++i){
//计算u,max2
double u=(q[i+1].d-q[i].d)/d2,max2=(q[n+1].d-q[i].d)/d2;
max2=min1(max2,c);w=0;
if(u>c) {
printf("No Solution");
return 0;
}
//若加满了油还不能从i到i+1说明无法到达目的地,直接终止程序
//枚举第i个加油站后哪一些加油站(连续的)比第i个加油站的加油费贵
//j枚举到n+1是为了让w可以为目的地那个点
for(int j=i+1;j<=n+1;++j){
/*已忽略的加油站不需再替那段路程加油了,若遇到了更
贵的加油费的加油站要停止*/
if(q[i].p<q[j].p&&!book[j]){
//若已有的油加上从j地到j+1地所需要的油比max2大就加油加到max2
//计算ans,c1(这里就不加说明了)
if(c1+(q[j+1].d-q[j].d)/d2>=max2){
ans+=(max2-c1)*q[i].p;
c1=max2;break;//既然满了,那么就可以退出了
}
//反之加上从j地到j+1地所需要的油
else{
ans+=(q[j+1].d-q[j].d)/d2*q[i].p;
c1+=(q[j+1].d-q[j].d)/d2;
}
}
else {w=j;break;}//给w赋值
}
for(int v=1;v<w;++v) book[v]=1;//标记
//还记得吗,我们还没加上从i地到i+1地所需的油量,那么这些油加不加就看下面的了
//关键,如果此时的油量小于到w地所需的油量,就需加上**适量**的油
if(c1<(q[w].d-q[i].d)/d2) {
/*如果从i地到w地所需的油量小于max2那么加油,一直加
到(q[w].d-q[i].d)/d2,反之加到max2即可*/
if((q[w].d-q[i].d)/d2<=max2){
ans+=((q[w].d-q[i].d)/d2-c1)*q[i].p;
c1=(q[w].d-q[i].d)/d2;
}
else ans+=(max2-c1)*q[i].p,c1=max2;
}
c1-=u;//减去从i地到i+1地所需的油,为下站做准备
}
if((d1-q[n].d)/d2>c){
printf("No Solution");
return 0;
}//若加满了油还不能从第n个加油站到达目的地说明不能到达目的地
ans+=((d1-q[n].d)/d2-c1)*q[n].p;
//记住到了n地,油箱不知道有多少油,所以在这里还得再算一下油钱
printf("%.2lf",ans);//保留2位
return 0;
}
```
by whwh @ 2019-06-07 08:05:45