P8162 [JOI 2022 Final] 让我们赢得选举 (Let's Win the Election) 题解

朴素的想法是先抓一部分人，再一起去发表演讲。这样就要按 \(b\) 的值从小到大排序，枚举选择的一部分 \(b\) 值，在后面挑选一些最小的 \(a\) 选择即可。

但这样显然是错误的。观察到 \(n\le 500\)，显然是 \(O(n^3)\) 的复杂度，但这样大致是 \(O(n^2)\) 的。考虑这样的策略会使什么情况不优。

注意到先抓人的策略一定没有问题，但问题出在抓的人不一定是按 \(b\) 值排序的前一部分。当一个 \(a\) 特别小的时候，我们完全可以不选 \(b\) 而去选 \(a\)，抓完人之后补上选票即可。看上去这个东西不是很好操作，但是注意到前面的这一部分不选 \(b\) 的条件是选 \(a\)，也就是说不论怎样都会获得选票，于是考虑枚举最后一个抓人的点，抓人的点之前的部分一定是选择 \(a/b\)，对于记录抓人个数可以用容易的 \(O(n^2)\) dp 实现；对于后面的部分预处理最小值即可。时间复杂度是 \(O(n^3)\) 的。

代码：

#include <bits/stdc++.h>
#define db double
#define N 505
using namespace std;
int n, k;
struct Node {
	db a, b;
	bool operator < (const Node &x) const {
		return b < x.b;
	}
} e[N];
db dp[N][N];
void ck(db &x, db y) {
	x = min(x, y);
}
db ans = 1e9;
db sum[N][N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> e[i].a >> e[i].b;
		if (e[i].b == -1) e[i].b = 1e9;
	}
	sort(e + 1, e + 1 + n);
	for (int i = 0; i <= n; i++) {
		vector<db>v;
		v.push_back(-1);
		for (int j = i + 1; j <= n; j++)
			v.push_back(e[j].a);
		sort(v.begin(), v.end());
		int l = v.size();
		for (int j = 1; j <= l; j++)
			sum[i][j] = sum[i][j - 1] + v[j];
	}
	for (int nb = 0; nb <= n; nb++) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				dp[i][j] = 1e9;
		dp[0][0] = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= min(i, nb); j++)
				if (dp[i][j] < 1e9) {
					ck(dp[i + 1][j], dp[i][j] + e[i + 1].a / (nb + 1));
					ck(dp[i + 1][j + 1], dp[i][j] + e[i + 1].b / (j + 1));
				}
		for (int i = 0; i <= n; i++)
			ck(ans, dp[i][nb] + sum[i][k - i] / (nb + 1));
	}
	printf("%.10lf\n", ans);
	return 0;
}