AT2402 [ARC072D] Dam

tony102

2020 年 11 月 26 日

1770 次浏览

暂无评论

752字数

题解

[Link](https://www.luogu.com.cn/problem/AT2402)

墙裂推荐的好题

## Sol

首先考虑一些特殊的情况.

假如每天流进来的水的温度都是递减的,那么我们肯定希望前面的水多一些,后面的水少一些.

假如每天流进来的水温度都是递增的,那么相当于把递减的情况反过来,也就是选出一段后缀.但是在溢出的时候要用一个双指针来维护一下把一些水给倒掉.

现在来想想正解

有了上面两个特殊情况的启发. 在 $t_i > t_{i-1}$ 的时候我们会让他们尽可能少地混合, 要尽可能地多弄温度为 $t_i$  的水. 相反就要尽可能多地混合.

所以可以维护一个单调队列, 队列中的每个元素就是一段水混合在一起.

溢出的时候直接把队头一段温度比较小的丢掉即可. 然后把现在的水加进队列. 判一下如果 $t_{tail-1} > t_{tail}$, 那么这个水会破坏队列的单调性,就把他和 $tail-1$ 的水混在一起就可以了

中途维护一下总热量, 每次除以 $L$ 就是答案了

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

const int SIZE = 5e5 + 5;

int n, L;
double t[SIZE], v[SIZE];

struct node {
	int v; double t;
} q[SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

signed main() {
	// freopen("crescendo.in", "r", stdin);
	// freopen("crescendo.out", "w", stdout);
	n = read(), L = read();
	for (int i = 1, ti, vi; i <= n; ++ i) {
		ti = read(), vi = read();
		t[i] = ti * 1.0000, v[i] = vi * 1.0000;
	}
	int head = 1, tail = 0;
	int curV = 0; double curT = 0.00000, ans = 0.0000;
	for (int i = 1; i <= n; ++ i) {
		while (curV + v[i] > L) {
			int del = std::min(q[head].v, curV - (L - (int) v[i]));
			q[head].v -= del, curV -= del; ans -= q[head].t * del;
			if (!q[head].v) ++ head;
		}	
		curV = L, ans += t[i] * v[i];
		++ tail; q[tail].t = t[i], q[tail].v = v[i];
		while (head < tail && q[tail - 1].t > q[tail].t) {
			q[tail - 1].t =
			((q[tail - 1].v * q[tail - 1].t) + (q[tail].v * q[tail].t)) / (q[tail - 1].v += q[tail].v);
			-- tail;
		}
		printf("%.7Lf\n", ans / L);
	}
	return 0;
}
```

最后修改：2021 年 08 月 20 日