P1016 [NOIP1999 提高组] 旅行家的预算

#include<bits/stdc++.h>
using namespace std;
double maxd,d1,d2,c,P,nd,now,ans;
int n;
double d[10],p[10];
deque<pair<double,double> > de;//first表示距离 second表示价值 
int main(){
	scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&P,&n);
	p[n+1]=0;
	d[n+1]=d1; 
	p[0]=P;
	d[0]=0;
	maxd=d2*c;//加满油最长能行驶距离 
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&d[i],&p[i]);
	for(int i=1;i<=n+1;i++)
		if(d[i]-d[i-1]>c*d2){
			printf("No Solution");//判断不可行解 
			return 0; 
		}
	for(int i=0;i<=n;i++){
		while(!de.empty()&&d[i]-de.front().first>=maxd)de.pop_front();//单调队列first过小 
		while(!de.empty()&&de.back().second>p[i])de.pop_back();//单调队列优化second 
		de.push_back(make_pair(d[i],p[i]));
		ans+=(d[i+1]-d[i])/d2*de.front().second;
	} 
	printf("%.2lf",ans);
	return 0;
}

评测结果