[CSP-J 2020] 直播获奖

GitHub跳转原题关系图返回列表

用树状数组维护 0..600 的成绩频率，并通过第 k 小查询在线求当前获奖分数线。

OJ: luogu

题目 ID: P7072

难度:普及-

标签:树状数组计数模拟python

日期: 2026-06-19 00:26

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

成绩依次公布。公布第 seen 个成绩后，取排名前 max(1, seen*w//100) 人中的最低成绩作为当前分数线。

思路

成绩只在 0..600，用树状数组保存每个分数的出现次数。若当前有 winners 人获奖，分数线就是升序第 seen-winners+1 个成绩。树状数组的倍增查找可以在 O(log⁡601)O(\log 601) 找到这个次序统计量。

全程只用整数计算获奖人数，避免浮点向下取整误差。

Python 知识

  • enumerate(data, 1) 直接得到当前已公布人数。
  • int.bit_length() 取得树状数组倍增搜索的最高二进制步长。
  • 分数范围虽小，Fenwick 写法比每轮倒扫 601 个桶更适合 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)

复杂度

时间复杂度 O(nlog⁡601)O(n\log 601)，空间复杂度 O(601)O(601)。

总结

动态分数线本质是频率数组上的第 kk 小查询。