NOI2130 获奖分数线实时查询：算法解析与代码实现

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 p 个选手的成绩，则当前计划获奖人数为 max(1,⌊p∗w%⌋)，其中 w 是获奖百分比，⌊x⌋ 表示对 x 向下取整，max(x,y) 表示 x 和 y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

现在给出 n 个选手的成绩，你需要在每一轮评分后，即时输出当前的获奖分数线。

输入格式

第一行包含整数 n 和 w，表示选手数量和获奖百分比。

第二行包含 n 个整数，表示每个选手的成绩。

输出格式

共 n 行，每行一个整数，表示当前的获奖分数线。

数据范围

1≤n≤105, 0≤w≤100, 选手的成绩不超过 106。

输入样例：

10 30 10 9 8 7 6 5 4 3 2 1

输出样例：

3 3 3 4 4 4 5 6 7 8

算法1

(排序+前缀和) $O(nlogn)$

时间复杂度

$O(nlogn)$，主要由排序操作决定。

参考文献

排序算法

python3 代码

n, w = map(int, input().split())
scores = list(map(int, input().split()))
scores.sort()

prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i + 1] = prefix_sum[i] + scores[i]

for i in range(n):
    target_count = max(1, (i + 1) * w // 100)
    print(scores[prefix_sum[target_count] - 1])

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    int scores[n];
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
    }
    sort(scores, scores + n);

    long long prefix_sum[n + 1] = {0};
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + scores[i];
    }

    for (int i = 0; i < n; ++i) {
        int target_count = max(1, (i + 1) * w / 100);
        cout << scores[prefix_sum[target_count] - 1] << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

$O(n^2)$，对于每个选手，都需要遍历前面的选手。

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    int scores[n];
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
    }
    sort(scores, scores + n);

    for (int i = 0; i < n; ++i) {
        int target_count = max(1, (i + 1) * w / 100);
        cout << scores[target_count - 1] << endl;
    }
    return 0;
}