用树状数组维护 0..600 的成绩频率，并通过第 k 小查询在线求当前获奖分数线。
启发题
启发记录： 桶排序模板题目
OJ: luogu
题目 ID: P7072
难度:普及-
标签:树状数组计数模拟桶排序模板python
创建: 2026-06-19 00:26
更新: 2026-10-11 19:49
题意
成绩依次公布。公布第 seen 个成绩后，取排名前 max(1, seen*w//100) 人中的最低成绩作为当前分数线。
思路
成绩只在 0..600，用树状数组保存每个分数的出现次数。若当前有 winners 人获奖，分数线就是升序第 seen-winners+1 个成绩。树状数组的倍增查找可以在
全程只用整数计算获奖人数，避免浮点向下取整误差。
Python 知识
enumerate(data, 1)直接得到当前已公布人数。int.bit_length()取得树状数组倍增搜索的最高二进制步长。- 分数范围虽小，Fenwick 写法比每轮倒扫 601 个桶更适合 Python 的循环性能。
代码
正式主解（Python，树状数组倍增求第
python
import sys
data = iter(map(int, sys.stdin.buffer.read().split()))
n, percentage = next(data), next(data)
tree = [0] * 602
def add(index):
index += 1
while index < len(tree):
tree[index] += 1
index += index & -index
def kth(k):
index = 0
step = 1 << (len(tree).bit_length() - 1)
while step:
next_index = index + step
if next_index < len(tree) and tree[next_index] < k:
index = next_index
k -= tree[next_index]
step >>= 1
return index
answer = []
for seen, score in enumerate(data, 1):
add(score)
winners = max(1, seen * percentage // 100)
answer.append(kth(seen - winners + 1))
print(*answer)C++ 参考实现（值域只有
cpp
#include <bits/stdc++.h>
using namespace std;
// main.cpp：P7072 直播获奖（CSP-J 2020）
// 思路：成绩只有 0~600，用 cnt[s] 统计已出分人数，
// 每出一个分就从高分往低分累加，找到累计人数 >= 计划获奖人数的第一个分数，即分数线。
// 复杂度：每次询问最多扫 601 个分数，总复杂度 O(n * 600)。
const int MAXN = 100005;
const int MAXS = 600; // 成绩上界（题面成绩 0~600）
int n; // 选手总数
int w; // 获奖百分比（w%）
int a[MAXN]; // a[i] = 第 i 个出分选手的成绩
int cnt[MAXS + 5]; // cnt[s] = 已出分选手中成绩恰为 s 的人数（值域小，直接开桶）
// 求即时分数线：从高分往低分累加人数，
// 累计到第 need 名时所在的分数就是第 need 名的成绩（并列同分自然都获奖）。
int get_line(int need) {
int sum = 0;
for (int score = MAXS; score >= 0; score--) {
sum += cnt[score];
if (sum >= need) {
return score;
}
}
return 0; // 兜底：全部为 0 分时返回 0
}
// 逐个加入成绩并输出当前分数线
void solve() {
for (int i = 1; i <= n; i++) {
cnt[a[i]]++; // 第 i 个选手出分，进桶
int need = i * w / 100; // 计划获奖人数 floor(i * w%)
if (need < 1) {
need = 1; // 至少 1 人获奖（题面 max(1, ...)）
}
int line = get_line(need); // 当前获奖分数线
if (i > 1) {
cout << ' '; // 相邻整数间用一个空格分隔
}
cout << line;
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); // 关掉同步，加快读入（本题 n 可达 1e5，影响不大但属习惯写法）
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
solve();
return 0;
}复杂度
Python 版时间复杂度
C++ 版每次询问最多倒扫 601 个桶，时间复杂度
总结
动态分数线本质是频率数组上的第
