5 August

P1016 旅行家的预算

单调队列。

再看看单调队列怎么用的。

#include <cstdio>

int n, l, r;

double D, dd, d[9], C, p[9], ans;

struct node{

	double t, x;

} q[999];

int main() {

	scanf("%lf%lf%lf%lf%d", &D, &C, &dd, &p[0], &n); d[0]=0;

	for (int i=1; i<=n; ++i) {

		scanf("%lf%lf", &d[i], &p[i]);

		if (d[i]-d[i-1]>C*dd) {printf("No Solution\n"); return 0; }

	}

	d[n+1]=D; double now=0.0;

	q[++r]=(node){p[0], now=C}, ans+=p[0]*C;

	for (int i=1; i<=n+1; ++i) {

		double cos=(d[i]-d[i-1])/dd;

		while (l<=r && cos>0) {

			if (q[l].x>cos) {now-=cos, q[l].x-=cos; break; }

			now-=q[l].x, cos-=q[l].x; ++l;

		}

		if (i==n+1) {

			while (l<=r) ans-=q[l].t * q[l].x, ++l; break;

		}

		while (l<=r && q[r].t>p[i]) {

			ans-=q[r].t*q[r].x, now-=q[r].x; --r;

		}

		ans+=(C-now)*p[i];

		q[++r]=(node){p[i], C-now}; now=C;

	}

	printf("%.2lf\n", ans);

	return 0;

}

巴特西

5 August

最新文章

热门文章