Dropping tests

题目解析

题意：有 $n$ 次考试，第 $i$ 次得了 $a_i$ 分（满分 $b_i$ 分）。允许丢掉其中 $k$ 次，使剩下 $n-k$ 次的累计平均分 $100 \cdot \dfrac{\sum a_i}{\sum b_i}$ 尽可能大，输出四舍五入到整数的最大百分比。

1. 二分性（单调性）

二分性：如果分数 $x$ 可以达到，那么比 $x$ 更小的分数都能达到（沿用同一组考试即可）。即 $query_{max\_sum}(x) \geqslant 0$ 成立时，任意 $x_i < x$ 也都成立。因此可以对答案 $x$ 本身二分，我们要让 $x$ 尽可能大。
答案范围： $[0, 1]$ （输出时再乘 100）。

于是问题变成：给定 $x$ ，判定「是否存在一种丢弃方案，使平均分至少为 $x$ 」。

2. 分数规划变形（关键观察）

验证 $x$ 可达，就是问是否存在一组 $S$ （ $|S| = n-k$ ）满足：

\frac{\sum_{i \in S} a_i}{\sum_{i \in S} b_i} \geqslant x

两边乘正数 $\sum_{i \in S} b_i$ ，并按考试 $i$ 整理：

\sum_{i \in S} (a_i - x \cdot b_i) \geqslant 0

定义 $v_i = a_i - x \cdot b_i$ ，「比率 $\geqslant x$ 」就被转成「选出的 $v_i$ 之和 $\geqslant 0$ 」。这一步是 01 分数规划的灵魂：把分式判定变成线性求和判定，把分子分母联动的困难消掉。

3. check 函数：贪心取最大的 $n-k$ 个

要让 $\sum v_i$ 尽可能大，显然应该选 $v_i$ 最大的 $n-k$ 个。若它们的和仍然 $< 0$ ，任何选法都不可能达到 $x$ ；否则 $x$ 可达（甚至可能更高）。

代码对应：_sum(x) 计算所有 $v_i$ 、排序后累加末尾 $n-k$ 个；check(mid) 返回 _sum(mid) >= 0。

4. 二分与输出

在 $[0, 1]$ 上固定二分 100 次：每次取 $mid = (l+r)/2$ ，check(mid) 为真则 l = mid，否则 r = mid。100 次后区间长度缩到 $2^{-100}$ ，远超输出精度需要。
最后输出 (int)(l*100 + 0.5)，即四舍五入后的百分比。

5. 复杂度

每次 check 需要 $O(n \log n)$ 排序，二分固定 100 次，总计 $O(100 \cdot n \log n)$ ；额外空间 $O(n)$ 存放 $v_i$ 。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-05 15:28:43
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,k;
int a[maxn];
int b[maxn];
double v[maxn]; // v[i] = a[i] - x * b[i] 

double _sum(double x) {
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        v[i] = a[i] -  x * b[i];
    }
    std::sort(v+1,v+1+n);

    // 这里是贪心, 选的越少越好, 哪就选 n-k个
    double s = 0;
    for(int i = n;i >k;--i ) // i: 1->n
        s+= v[i];
    return s;
}

//检查pos位置的值是否符合要求
bool check(double mid){
    return _sum(mid) >= 0;
}



signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    while (1) {
        std::cin >> n >> k;
        if( n == 0 &&k == 0) break;
        for(int i = 1;i <= n ;++i ) // i: 1->n
            std::cin >> a[i];
        for(int i = 1;i <= n ;++i ) // i: 1->n
            std::cin >> b[i];

        // 枚举分数
        double l = 0 , r = 1;

        //100 次 应该可以了
        for(int i = 0 ;i < 100 ;i++)
        {
            double mid = (l+r) / 2;
            if( check(mid)) 
                l = mid;
            else
                r = mid;

        }
        std::cout << (int)(l*100 + 0.5) << "\n";
        
    }
    
    return 0;
}

目录