luoguP2989 [USACO10MAR]Need For Speed S

01分数规划

思路

一眼望过去就是01分数规划的板子题，但又要求保证 $M + \sum M_i X_i$ 最小

结论是：按照 $\frac{F_i}{M_i}$ 降序排序可以保证

证明：反设无法保证，那么，对于当前二分的答案 $e$ ，存在 $a, b, c, d$ 满足：

$a$ 是已选中的但不在最优答案的 $i$ 的 $F_i$ 之和
$b$ 是已选中的但不在最优答案的 $i$ 的 $M_i$ 之和
$c$ 是未选中的但在最优答案的 $i$ 的 $F_i$ 之和
$d$ 是未选中的但在最优答案的 $i$ 的 $M_i$ 之和

再设 $e = \frac{A}{B}$ ，那么有：
$$
\begin{aligned}
& \frac{A - a + c}{B - b + d} = e \\
\Rightarrow & \frac{a - c}{b - d} = e
\end{aligned}
$$
且 $b > d$ （因为 $c, d$ 更优）

不妨设 $a = c + ke$ （这个 $k$ 不是题目中的 $k$ ），则 $b = d + k$ ，那么由于我们假设的是无法保证，所以 $\frac{c}{d}$ 排在 $\frac{a}{b}$ 的后面，即：
$$
\begin{aligned}
& \frac{c + ke}{d + k} > \frac{c}{d} \\
\Rightarrow & ed > c
\end{aligned}
$$
但考虑设 $A’ = A - a, B’ = B - b$ ，有 $\frac{A’ + c}{B’ + d} = e$ ，必有 $\frac{c}{d} > e$ ，因为如果 $\frac{c}{d} < e$ ，我们可推得 $\frac{A’}{B’} > e$ ，选了反而让答案变小，这和 $c, d$ 是最优解矛盾，所以 $\frac{c}{d} > e$ ，那么有 $c > ed$ ，又矛盾

综上，原命题成立

代码

#include <bits/stdc++.h>
using DB = double;
const DB eps = 1e-6;
const int N = 1e4 + 100, INF = 0x3f3f3f3f;
int n;
DB m, f;
struct Node{ DB f, m; int id; } a[N];
std::vector<int> ans, as;
int cmp(DB x, DB y)
{
    if (fabs(x - y) < eps) return 0;
    return x > y ? 1 : -1;
}
bool chk(DB x)
{
	as.clear();
	DB t = m * x - f, sum = 0;
	for (int i = 1; i <= n; ++i) if (cmp(a[i].f - a[i].m * x, 0) == 1) 
	{
		as.push_back(a[i].id);
		sum += a[i].f - a[i].m * x;
		if (cmp(sum, t) != -1) break;
	}
	if (cmp(sum, t) != -1)
	{
		ans = as;
		return true;
	}
	return false;
}
int main()
{
	scanf("%lf %lf %d", &f, &m, &n);
	for (int i = 1; i <= n; ++i) scanf("%lf %lf", &a[i].f, &a[i].m), a[i].id = i;
	std::sort(a + 1, a + n + 1, [&](Node x, Node y){ return x.f * y.m > y.f * x.m; });
	DB l = 0, r = INF, mid;
	while (cmp(l, r) == -1)
	{
		mid = (l + r) / 2;
		if (chk(mid)) l = mid;
		else r = mid;
	}
	std::sort(ans.begin(), ans.end());
	if (!ans.size()) puts("NONE");
	else for (int i : ans) printf("%d\n", i);
	return 0;
}