专栏文章

题解：SP110 CISTFILL - Fill the Cisterns

gggc123
SP110题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miokxiaj
此快照首次捕获于
2025/12/02 20:53
3 个月前
此快照最后确认于
2025/12/02 20:53
3 个月前
查看原文

思路

对于本题而言，直接通过这些水箱求出答案过于困难。但是不难发现：水位越高，这个容器装的水越多（二分的单调性）。由此可以得到本体考察的是二分。
我们二分答案，对于每一个我们二分出来的答案，去对比当前水位装下的水的体积和给定体积的大小关系。
对于水溢出的情况，我们只需验证所有水箱的容积是否小于水的体积即可。

代码

CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 50005;

struct A {
	int b, h, w, d;
} a[N];
int T, n, v;

bool check(double x) {
	double cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += min(max(x - a[i].b, 0.0), (double)a[i].h) * a[i].d * a[i].w;
	return cnt >= v;
}
bool flag() {
	double cnt = 0;
	for (int i = 1; i <= n; i++) cnt += a[i].h * a[i].d * a[i].w;
	return cnt >= v;
}

signed main() {
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i].b >> a[i].h >> a[i].w >> a[i].d;
		cin >> v;

		if (!flag()) {
			cout << "OVERFLOW \n";
			continue;
		}

		double L = 0, R = 2e6, mid, ans;
		while (abs(R - L) >= 1e-5) {
			mid = (L + R) / 2.0;
			if (check(mid))
				ans = R = mid;
			else
				L = mid;
		}
		cout << fixed << setprecision(2) << ans << "\n";
	}

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...