「JOI 2022 Final」Let's Win the Election

#题面

#题目描述

JOI 共和国由 $N$ 个州组成，现在 JOI 共和国正在进行选举。

理恵想要赢得选举，她决定以发表演讲的方式来提高自己的支持率，具体的，她可以发表任意时间长度的演讲，这些演讲会造成一定的影响：

• 如果在这个州的演讲时间达到 $A_i$，那么她将会赢得一张选票；
• 如果在这个州的演讲时间达到 $B_i$，那么她将会赢得一名协作者，协作者可以与她同时在任何州发表演讲，如果多人同时在一个州发表演讲，计入多倍演讲时间。
• 有可能无法获得协作者，此时 $B_i=-1$，此外我们保证 $B_i\ge A_i$。

理恵想尽快得到 $K$ 张选票，请计算最小的演讲时间。

#输入格式

第一行一个整数 $N$。

第二行一个整数 $K$。

接下来 $N$ 行，一行两个整数 $A_i,B_i$。

#输出格式

输出一个实数，表示需要的最小演讲时间，你的答案与标准答案的绝对误差不应超过 $0.01$。

#输入输出样例

样例输入 #1

3
3
1 5
2 3
4 5

样例输出 #1

5.500000000000000

样例解释 #1

方案如下：

• 在第 $2$ 个州演讲 $3$ 个小时，获得一张选票和一个协作者。
• 在第 $3$ 个州与协作者一起演讲 $2$ 个小时，获得一张选票。
• 在第 $1$ 个州与协作者一起演讲 $0.5$ 个小时，获得一张选票。

这个样例满足子任务 $3,4,5,6,7$​ 的性质。

样例输入 #2

7
4
4 -1
11 -1
6 -1
12 -1
36 -1
11 -1
20 -1

样例输出 #2

32.000000000000000

样例解释 #2

选择第 $1,2,3,6$ 个州演讲是最优的。

这个样例满足子任务 $1,2,3,4,5,7$ 的性质。

样例输入 #3

5
3
4 -1
5 -1
6 -1
7 7
8 8

样例输出 #3

11.500000000000000

样例解释 #3

方案如下：

• 在第 $4$ 个州演讲 $7$ 个小时，获得一张选票和一个协作者。
• 在第 $1$ 个州演讲 $4$ 个小时，获得一张选票，同时让协作者在第 $2$ 个州演讲 $4$ 个小时。
• 在第 $2$ 个州与协作者一起演讲 $0.5$ 个小时，获得一张选票。

这个样例满足子任务 $2,3,4,5,7$ 的性质。

样例输入 #4

7
5
28 36
11 57
20 35
19 27
31 33
25 56
38 51

样例输出 #4

62.166666666666664

样例解释 #4

这个样例满足子任务 $3,4,5,7$ 的性质。

样例输入 #5

20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260

样例输出 #5

644.203571428571422

样例解释 #5

这个样例满足子任务 $4,5,7$ 的性质。

#数据范围与约定

对于全部数据，$1\le N\le 500$，$1\le K\le N$，$1\le A_i\le 10^3$，$A_i\le B_i\le 10^3$ 或者 $B_i=-1$。

#思路

原题面可以转化为：

给出一个长度为 $n$ 的序列，从中选出 $k$ 个元素，设 $c = 1$，对于这 $k$ 个元素，在排序后有以下操作：

1. 耗费 $\frac{a_i}{c}$ 的时间处理这个元素；
2. 耗费 $\frac{b_i}{c}$ 的时间处理这个元素并使 $c$ 增加 $1$。

求处理完全部 $k$ 个元素的最小花费。

显然先进行操作 2 比先进行操作 1 要优，并且优先选择 $b_i$ 小的比其他方式优。

然后考虑 DP。设 $f_{i, j}$ 表示在前 $i$ 个州中招收协作者的最小耗时，其中 $i$ 表示当前所处的州的编号，$j$ 表示到达当前状态获得了多少协作者。再预处理出 $g_{i, j}$ 表示在 $a_{i \sim n}$ 中前 $j$ 小的数的总和。最后将 $f$ 和 $g$ 中对应的值相加即可。

详细实现可以查看下方代码。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 505;

int n, k;
std::pair<int, unsigned int> p[N], q[N];
double f[N][N], g[N][N], ans = 1e9;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> p[i].first >> p[i].second;
    }

    std::sort(p + 1, p + 1 + n, [&](auto a, auto b) -> bool {
        return a.second < b.second;
    });

    for (int i = 1; i <= n; i++) {
        q[i] = p[i];
    }

    // 预处理 i ~ n 中 a_i 的前 j 小之和
    for (int i = n; i; i--) {
        std::sort(q + i, q + 1 + n, [&](auto a, auto b) -> bool {
            return a.first < b.first;
        });

        for (int j = i; j <= n; j++) {
            g[i][j - i + 1] = g[i][j - i] + q[j].first;
        }
    }

    for (int t = 0; t < k; t++) {  // 枚举招纳协作者的数量
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= t; j++) {
                f[i][j] = 1e9;
            }
        }

        f[0][0] = 0;  // 演讲前耗时为 0

        for (int i = 1; i <= k; i++) {
            // 还未招协作者的时候直接从上一次转移
            f[i][0] = f[i - 1][0] + static_cast<double>(p[i].first) / (t + 1);  // 还要加上 Rie 本人

            for (int j = 1; j <= t; j++) {
                f[i][j] = std::min(
                    f[i - 1][j - 1] + static_cast<double>(p[i].second) / j,    // 需要招协作者的立即演讲
                    f[i - 1][j] + static_cast<double>(p[i].first) / (t + 1));  // 不招协作者的在招满后再演讲
            }
        }

        for (int i = 0; i <= k; i++) {
            ans = std::min(ans, f[i][t] + g[i + 1][k - i] / (t + 1));  // 增加协作者耗时 + 纯演讲耗时
        }
    }

    cout << std::fixed << std::setprecision(15) << ans << endl;

    return 0;
}