旅行家的预算

洛谷P1016

大佬的博客

又是抄的题解。。。自己做的时候一定要多想想可能的情况，因为考试只有一次机会。
注释写在代码里了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 9999999
using namespace std;
const int N = 50005;
int n;
double d1,c,d2,po,ans,res,maxx;
struct node{
	double d,p;
	bool friend operator < (const node& a,const node& b)
	{ return a.d<b.d;}//立后习惯用重载运算符吧，cmp 玄学 
}a[N]; 
//bool cmp(node x,node y)
//{ return x.d<y.d; } 
int work(int now)
{
	int flag=inf;
	double dis=a[now].d;
	for(int i=now+1;i<=n&&a[i].d-dis<=maxx;i++)
	{
		if(a[i].p<a[now].p)
		{//res是当前邮箱里的油还能走的路程  
			ans+=((a[i].d-dis-res)/d2)*a[now].p;
			res=0; return i;
		}//找到最近的油价比当前便宜的加油站  
		if(flag==inf||a[i].p<a[flag].p) flag=i; //如果没有比当前便宜的，
		//找一个能到达的加油站中最便宜的加油站  
	}
	if(d1-a[now].d<=maxx)
	{//如果没有找到比当前便宜的加油站（找到的话会return掉） 
		ans+=((d1-a[now].d-res)/d2)*a[now].p;
		return inf;//并且能直接到终点，就直接走到终点（后面的油都更贵） 
	}//如果没有当前加油站能到达的加油站，无解  
	if(flag==inf) { printf("No Solution
"); return -1; }
	else 
	{//否者加满油，为了避免在以后更贵的油站加油 
		ans+=c*a[now].p;//走到所能到达的油站中最便宜的  
		res+=(maxx-(a[flag].d-dis));
		return flag;
	}
}
int main()
{
	scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&po,&n);
	a[0].d=0; a[0].p=po;
	for(int i=1;i<=n;i++)
	 scanf("%lf%lf",&a[i].d,&a[i].p);
	sort(a,a+1+n);
	maxx=c*d2;
	int k=0,t;
	while(t!=inf)
	{
		t=work(k),k=t;
		if(t==-1) return 0; 
	} 
	printf("%.2lf
",ans);
	return 0;
}