直播获奖

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

成绩值域只有 0 到 600，用桶计数实时统计各分数人数，再从高分档向低分档累加到计划获奖人数，即得即时分数线。

OJ: roj

题目 ID: 3665

难度:普及-

标签:python桶计数计数

创建: 2026-10-02 14:22

更新: 2026-10-07 13:50

前置题目
roj 1067整数的个数B 的「入桶」步骤正是复用 A 教的桶计数：当值域极小时按值维护计数、扫一遍完成统计，B 把它从三个固定计数器推广为 601 档数组roj 1115直方图B 的优化第一步直接复用 A 教的「值当下标开桶、读入时桶加一」计数手法，再在其上叠加从高分档向下累加求第 k 名的新流程shumeng CSP202104A灰度直方图B 的入桶步骤直接复用了 A 教的按值分桶 count[x]++：把灰度值换成 0..600 的分数，累计频次后再从高分档向下累加定位第 k 名，从而在线求出分数线。
相似题目
luogu P7072[CSP-J 2020] 直播获奖洛谷上的同一道题（CSP-J 2020），其题解改用树状数组做第 k 小查询，可与本文的桶扫描对照

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

依次公布 nn 个成绩（每个为 0..6000..600 的整数），另有获奖百分比 ww（1≤w≤991 \le w \le 99）。每公布第 pp 个成绩，立刻输出当时的获奖分数线：计划获奖人数 kp=max⁡(1,⌊p⋅w/100⌋)k_p = \max(1, \lfloor p \cdot w / 100 \rfloor)，把已公布的 pp 个成绩从大到小排列，第 kpk_p 个成绩即为分数线；成绩相同者并列获奖。数据范围：n≤105n \le 10^5，成绩 ≤600\le 600。

思路

成绩值域只有 0..6000..600，用桶 cnt[s] 实时统计各分数人数，每读入一个成绩就入桶。查询时从 600600 分往低分累加人数，累加和首次达到 kpk_p 的那一档就是分数线。全程整数运算，避免浮点误差。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 14:25
# update_at: 2026-10-02 14:25

import sys

MAX_SCORE = 600  # 题面保证成绩为不超过 600 的非负整数，值域只有 601 档


def cutoff(cnt: list[int], need: int) -> int:
    """即时分数线：按名次从最高分往下累加，第 need 名落在哪个成绩上。"""
    got = 0
    for score in range(MAX_SCORE, -1, -1):
        got += cnt[score]
        if got >= need:
            return score
    return 0  # 不可达：need 不超过已评出的人数，全档累加必然凑满


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    w = next(data)
    cnt = [0] * (MAX_SCORE + 1)  # 每个成绩档的实时人数
    out: list[str] = []

    for p in range(1, n + 1):
        cnt[next(data)] += 1
        need = max(1, p * w // 100)  # 计划获奖人数：全程整数运算，避开浮点误差
        out.append(str(cutoff(cnt, need)))

    print(' '.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:14
 * update_at: 2026-10-06 16:14
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int MAX_SCORE = 600; // 成绩值域 0..600

int cnt[MAX_SCORE + 1];    // cnt[s] 表示成绩为 s 的人数

// 从高分往低分累加，找到第 need 名所在的成绩
int cutoff(int need) {
    int got = 0;
    for (int s = MAX_SCORE; s >= 0; --s) {
        got += cnt[s];
        if (got >= need) return s;
    }
    return 0; // 不可达
}

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

    int n, w;
    cin >> n >> w;

    for (int p = 1; p <= n; ++p) {
        int x;
        cin >> x;
        cnt[x]++;
        int need = max(1, p * w / 100); // 计划获奖人数，整数运算避浮点误差
        cout << cutoff(need);
        if (p < n) cout << ' ';
    }
    cout << '\n';
    return 0;
}