e
我这题是这样的,n记录站点,maxx表示最大行驶距离,t表示最远可以到的站点下标,l表示油箱剩油。
从n+1开始搜,比自己油价便宜的就停,n更新为那里,,n后面的所有站点距离减去D[n],D[n]再改为0。
如果没有比自己小的就加满油后开到区间油价最低处。
BUT。
输入:
475.6 11.9 27.4 14.98 6
102.0 9.99
220.0 13.29
256.3 14.79
275.0 10.29
277.6 11.29
381.8 10.09
输出:
192.15
我却是193.34,跪求帮助,谢谢。
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
#define db double
db D1,C,D2,P,D[10],p[10],maxx,s,l;
int N,n;
int main(){
cin>>D1>>C>>D2>>P>>N;
maxx=1.0*C*D2;
for(int i=1;i<=N;i++){
cin>>D[i]>>p[i];
}
p[0]=P;
D[N+1]=D1;
D[N+2]=0x7fffffff;
while(D[N+1]>0){
if(maxx<D[n+1]){
cout<<"No Solution";
return 0;
}
else{
int t=n;
bool ans=true;
while(D[++t]<=maxx);
t--;
for(int i=n+1;i<=t;i++){
if(p[i]<=p[n]){
ans=false;
s+=1.0*(1.0-1.0+1.0*D[i]/D2-l)*p[n];
l=0;
n=i;
for(int j=i+1;j<=N+1;j++){
D[j]-=D[i];
}
D[i]=0;
break;
}
}
if(ans){
db minn=p[n+1];
int minx;
for(int i=n+2;i<=t;i++){
if(p[i]<minn){
minn=p[i];
minx=i;
}
}
s+=1.0*(1.0-1.0+C-l)*minn;
l=C-1.0*D[minx]/D2;
for(int i=minx+1;i<=N+1;i++){
D[i]-=D[minx];
}
D[minx]=0;
n=minx;
}
}
}
cout<<fixed<<setprecision(2)<<s;
return 0;
}