75 pts 求助

单调队列写法

#include<bits/stdc++.h>
using namespace std;
typedef long long lol;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned int uin;

const int N = 9;
const double minn = 1e-5;
double dist, c, s, d[N], p[N], sum;
int n, q[N], hh, tt;

int main() {
//	freopen ("P1016_5.in", "r", stdin);
	scanf ("%lf%lf%lf%lf%d", &dist, &c, &s, &p[0], &n);
	++ n, c *= s, d[n] = dist, p[n] = 5005;
	for (int i = 1; i < n; ++ i ) 
		scanf ("%lf%lf", &d[i], &p[i]);
	
	bool suc = true;
//	printf ("dist   =   %lf\n", c);
//	printf (" -> %d %lf %lf\n", 0, d[0], p[0]);
	for (int i = 1; i <= n; ++ i ) 
	{
//		printf (" -> %d %lf %lf\n", i, d[i], p[i]);
		
		while (hh <= tt && p[i - 1] < p[q[tt]]) -- tt;
		q[++ tt] = i - 1;
		while (hh <= tt && d[q[hh]] + c < d[i]) ++ hh;
		
		if (hh <= tt) 
		{
			sum += (d[i] - d[i - 1]) * p[q[hh]] / s;
//			printf ("%d %lf\n", q[hh], sum);
		}
		else 
		{
			suc = false;
			break;
		}
	}
	
	if (!suc) puts ("No Solution");
	else printf ("%.2lf", sum);
	
	return 0;
}