题解：P15069 [UOI 2024 II Stage] Disco

· · 题解

题解：P15069 [UOI 2024 II Stage] Disco

形式化题意

给定 r_i、t_i 和 k，求一组 w_i \in \{0, 1\}，使得 \sum w_i = k 且 \frac {\sum r_i \times w_i}{\sum t_i \times w_i} 最大。

思路

分数规划板子题。

可以二分答案。设二分出来的答案为 mid，则有：

\frac {\sum r_i \times w_i}{\sum t_i \times w_i} \ge mid

转化：

\begin{aligned} &\frac {\sum r_i \times w_i}{\sum t_i \times w_i} \ge mid \\ \Rightarrow &\sum r_i \times w_i \ge mid \times \sum t_i \times w_i \\ \Rightarrow &\sum r_i \times w_i - mid \times \sum t_i \times w_i \ge 0 \\ \Rightarrow &\sum w_i \times (r_i - mid \times t_i) \ge 0\end{aligned}

在 check 时，只需要取 r_i - mid \times t_i 最大的 k 项之和判断是否大于等于 0 就可以了。

AC Code

#include <bits/stdc++.h>
using namespace std;
int n, k, a[100001], b[100001];
double c[100001];
bool check(double x) {
    for (int i = 1; i <= n; i++) {
        c[i] = a[i] - x * b[i]; // 计算值
    }
    sort(c + 1, c + n + 1);
    double tmp = 0;
    for (int i = n - k + 1; i <= n; i++) {
        tmp += c[i]; // 取最大的k项
    }
    return tmp >= 0;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    double l = 0, r = 1e10, mid;
    while (r - l >= 0.00001) { // 二分答案，注意误差
        mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l;
    return 0;
}

声明：此文章部分内容参考 OI Wiki。