Luogu P1016 旅行家的预算

Luogu P1016 旅行家的预算

首先将起点和终点与道路上的加油站视为等价节点，按照距离起点的距离（即通过顺序）排序。
然后对于每一个节点我们可以进行以下贪心策略：

• 如果可以直达下一个油价更低的加油站，就加满够到此加油站的油直接开过去。
• 如果不能直达，就加满油开到能到范围内油价最低的加油站。

注：读入的时候一定要看一下引用的变量被赋值了没！

#include<bits/stdc++.h>
#define N 10

using namespace std;

int n;
double d1,c,d2,ans;

struct node {
	double d,p;
	
}stage[N];

bool cmp(node a,node b) {
	return a.d<b.d;
}

void Read() {
	scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&stage[0].p,&n);
	stage[n+1].d=d1;
	for(int i=1;i<=n;i++) {
		scanf("%lf%lf",&stage[i].d,&stage[i].p);
	}
	return;
}

void Solve() {
	int now=0;
	double left=0;
	for(int i=1;i<=n;i++) {
		if(stage[i].d-stage[i-1].d>c*d2) {
			printf("No Solution");
			return;
		}
	}
	sort(stage+1,stage+n+1,cmp);
	while(now<=n+1) {
		int i,tmp=now+1;
		for(i=now+1;i<=n;i++) {
			if(stage[i].p<=stage[tmp].p) {
				tmp=i;
			}
			if(stage[i].p<=stage[now].p||c*d2<stage[i+1].d-stage[now].d) {
				break;
			}
		}
		if(stage[now].p<stage[i].p) {
			ans+=(c-left)*stage[now].p;
			left=c-(stage[tmp].d-stage[now].d)/d2;
            now=tmp;
		}
		else {
			ans+=stage[now].p*((stage[i].d-stage[now].d)/d2-left);
			now=i;
			left=0;
		}
	}
	printf("%.2lf",ans);
	return;
}

int main()
{
	Read();
	Solve();
	return 0;
}