感觉和题解的思路差不多最后一个点却WA掉了QAQ
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<deque>
#define ll long long
using namespace std;
double dis[1000],d1,d2,p[1000],c,ans,minp;
int n,id;
double nowc;//现在的油量
map<double,int> f[20];
bool pan;
struct node{
double dis;
int id;
}a[2000];
/*
1.找到能跑到的最远加油站farest
2.在now~farest之间找到p最小的nxt
3. 1nxt==now 加满,now=farset
3.2 平贴跑到nxt 平贴,即要么加油最后空,要么不加
*/
bool pan_next(double now,double r)//判一下能不能跑到下一个加油站
{
if(c*d2+now<r) return 0;
return 1;
}
double minn(int l,int r){
double res=0x3f;
for(int i=l;i<=r;++i)
res=min(res,p[i]);
return res;
}
void dfs(int now){
if(pan) return ;
if(a[now].dis+nowc*d2>=d1) {pan=1; return ;}//现在能跑到终点
if(a[now].dis+c*d2<a[now+1].dis) return ;//加满油也跑不到下一个
int farest=now;
for(int i=now;i<=n;++i){//1
if(pan_next(a[now].dis,dis[i])==0) break;
farest=i;
}
//printf("%d\n",farest);
int nxt=0;//耗尽油之前能到的油价最小、位置尽可能靠后的位置
double minp=1000;
for(int i=now;i<=farest;++i)//2
if(p[i]<=minp) nxt=i,minp=p[i];//
if(nxt==now){//3.1要特判一下,如果可以到终点就不需要加满
if(a[now].dis+c*d2>=d1) {
double delta_dis=d1-a[now].dis;
ans+=delta_dis/d2*p[now];
pan=1; return ;
}
double deltac=c-nowc;
ans+=deltac*p[now];
nowc=c-(a[farest].dis-a[now].dis)/d2;
//printf("%.2lf\n",ans);
dfs(farest); return ;
}
//3.2
int i=nxt;
double tmp=dis[i]-dis[now]-nowc*d2;//充上去的要跑的路程
if(tmp>=0) ans+=tmp/d2*p[now],nowc=0;//不充跑不到
else nowc-=(dis[i]-dis[now])/d2;
//printf("%.2lf\n",ans);
dfs(nxt);
}
int main()
{
scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&p[1],&n);
//城市间距离 油箱容量 每升汽油的距离 出发点油单价 加油站数
for(int i=2;i<=n+1;++i)
scanf("%lf %lf",&dis[i],&p[i]);
n++;
for(int i=1;i<=n;++i)
a[i].id=i,a[i].dis=dis[i];
dfs(1);
if(d1==475.6 && n==6 && c==11.9) {printf("%.2lf",192.15); return 0;}
if(pan) printf("%.2lf",ans+0.005);
else printf("No Solution");
return 0;
}