题解：P15069 [UOI 2024 II Stage] Disco

kmszcll2024 · 2026-01-27 11:22:43 · 题解

~~看标签而来。~~

本文主要介绍分数规划。

题意

不多赘述。

解题思路

使用分数规划。

分数规划是一种解决比值最大化 / 最小化问题的算法。

1. 基本形式

给定物品集合，每个物品有两个属性 a_i 和 b_i，要选择恰好 k 个物品，最大化比值：求 \max \frac{\sum a_i}{\sum b_i}。

2. 思想

1. 如果 \lambda 是可达到的比值

存在某个选择 X 使得：

\frac{\sum_{i \in X} a_i}{\sum_{i \in X} b_i} \geq \lambda

两边乘以分母（注意分母为正数）：

\sum_{i \in X} a_i \geq \lambda \sum_{i \in X} b_i

移项：

\sum_{i \in X} a_i - \lambda \sum_{i \in X} b_i \ge 0

等价于：

\sum_{i \in X} (a_i - \lambda b_i) \ge 0

2. 二分

对于猜测值 mid（也就是 \lambda）：

设实际的最大比值为 mx。

如果存在选择 X 使得 \sum (a_i - \text{mid} \cdot b_i) \geq 0
- 那么 mid 可以达到（或更小）
- mx \ge mid
- 所以我们可以尝试更大的值（提高下界）
如果对于所有选择 X，\sum (a_i - \text{mid} \cdot b_i) < 0
- 那么 mid 无法达到
- mx < mid
- 所以我们需要尝试更小的值（降低上界）

我的代码中使用了 nth_element 函数，不了解的同学戳这里。

在本题中，如上，二分即可。

除此题外，还有一道例题 p1404。

代码

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

const int N = 1e5 + 5;
int n, k;
int a[N], b[N];

bool check(double x) {
    vector<double> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = a[i] - x * b[i];
    }

    nth_element(c.begin(), c.begin() + k-1, c.end(), greater<double>());//降低时间复杂度。
    double s = 0;
    for (int i = 0; i < k; i++) {
        s += c[i];
    }
    return s >= 0;
}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int main() {
    n=read(),k=read();
    for (int i = 0; i < n; i++) a[i]=read();
    for (int i = 0; i < n; i++) b[i]=read();

    double l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        r = max(r, (double)a[i] / b[i]);
    }

    for (int i = 0; i < 30; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    printf("%.6lf", l);
    return 0;
}

我的代码目前是最优解。