#include <bits/stdc++.h> // 修正1：头文件
using namespace std;

int main(){
    int n, w;
    cin >> n >> w;
    int score[605] = {0}; // 稍微开大一点点，防越界
    
    for(int i = 0; i < n; i++){
        int s;
        cin >> s;
        score[s]++;
        
        // 修正2：人数应该是 i + 1，不是 i
        int cnt = max(1, (i + 1) * w / 100);
        
        int minscore = 0;
        int man = 0;
        // 倒序寻找第 cnt 个人
        for(int j = 600; j >= 0; j--){
            man += score[j];
            if(man >= cnt){
                minscore = j;
                break;
            }
        }
        
        //cout << minscore << " "; // 这样写通常没问题,也能AC
        cout << minscore;
        if(i < n - 1){
            cout << " ";
        }
    }
    return 0;
}

洛谷P7072 这道题（CSP-J 2020 T2 直播获奖）是一道非常经典的 “利用数据范围特征优化算法” 的题目。

如果只看 $N \le 10^5$，你可能会想到排序，但结合题目细节，你会发现排序会超时。我们要寻找更优的解法。

以下是解题思路提示：

1. 为什么“直接排序”会超时？

题目要求每进来一个新分数，就要输出一次当前的分数线。

• 如果有 $N$ 个人，你需要循环 $N$ 次。
• 在每次循环中，如果把所有成绩放入数组并调用 sort()（快排），复杂度是 $O(K \log K)$（$K$ 是当前人数）。
• 总复杂度大约是 $O(N^2 \log N)$。当 $N=100000$ 时，计算量远超 $10^8$，一定会 TLE（超时）。

即使你用插入排序（维护一个有序数组），插入的代价是 $O(K)$，总复杂度 $O(N^2)$，依然会超时。

2. 关键突破口：分数范围

请仔细看题目下方的【数据规模与约定】：

每个选手的成绩均为不超过 $600$ 的非负整数

这是一个极小的范围！

• 人数 $N$ 虽然多（10万），但分数的种类极少（只有 0 到 600，共 601 种可能）。
• 这意味着会有大量的人分数相同。

3. 核心思路：桶（计数排序思想）

既然分数范围这么小，我们为什么不直接统计**“每个分数有多少人”**呢？

算法流程：

1. 建立“桶”：定义一个大小为 605 的整数数组（例如 cnt[605]），初始化为 0。cnt[x] 用来存分数 $x$ 出现了多少次。
2. 动态读入：每读入一个新选手的成绩 score：
   • 不需要把 score 存进一个大列表里。
   • 直接在桶里做标记：cnt[score]++。
3. 计算排名：
   • 计算当前需要选拔的人数：k = max(1, i * w / 100) （注意利用整数除法自动向下取整的特性，不要用浮点数）。
   • 关键步骤：怎么找第 k 名的分数？
     • 我们从最高分 600 分开始往下遍历（从 600 到 0）。
     • 累加桶里的人数：sum += cnt[j]。
     • 一旦发现 sum >= k，说明第 k 名就在当前分数 j 这个档位里。
     • 输出 j，并 break 结束内层循环。

4. 复杂度分析

• 外层循环：遍历 $N$ 个人。
• 内层循环：最坏情况遍历 600 个桶。
• 总运算量：$600 \times 100,000 = 6 \times 10^7$。
• 计算机 1 秒大概能跑 $10^8$ 次，所以这个方法是非常稳的，可以 AC。

5. 代码框架提示

int bucket[605] = {0}; // 桶初始化
// 循环 i 从 1 到 n:
    cin >> score;
    bucket[score]++; // 入桶

    // 计算获奖人数 plan_num
    // 提示：C++整数除法 5/100 结果是0，所以要先乘后除： i * w / 100
    int plan_num = max(1, i * w / 100);

    int count = 0;
    // 从高分到低分扫描
    for (int j = 600; j >= 0; j--) {
        count += bucket[j]; // 累加人数
        if (count >= plan_num) {
            cout << j << " ";
            break; // 找到了立刻退出扫描
        }
    }

抓住“分数值域小”这个特征，用桶来代替排序，就是这道题的满分秘籍！加油！

---

这个解答错在哪？

#include <bits/stdc++>
using namespace std;

int main(){
    int n,w;
    cin>>n>>w;
    int score[601]={0};//分数的桶。利用bucket来计数，避免每次重新排序。
    for(int i=0;i<n;i++){
        int s=0;
        cin>>s;
        score[s]++;
        //当前获奖人数
        int cnt=max(1,i*w/100);
        //当前获奖分数线
        int minscore=600;
        int man=0;
        for(int j=600;j>=0;j--){
            man+=score[j];
            if(man>=cnt){
                minscore=j;//当前桶的分数就是获奖最低分数
                break;
            }
        }
        cout<<minscore;
        //最后一个不打印空格
        if(i<=n-1){
            cout<<" ";
        }
    }
}

你好！你的代码思路完全正确（使用了桶排序的思想），但是在细节实现上有两处错误，其中一处是致命的逻辑错误，会导致答案错误（WA）。

1. 致命逻辑错误：人数计算偏差

问题位置：

int cnt = max(1, i * w / 100);

原因分析：

• 循环变量 i 是从 0 开始的。
• 当循环进行到第 i 次时，实际上已经读入了 i + 1 个人的成绩。
• 题目要求的是“当前已评出了 $p$ 个选手的成绩”，这里的 $p$ 应该是 i + 1。

举例说明（假设 w=60）：

• 当 i=4 时，说明读入了 5 个人。
• 正确算法：应该用 5 个人来算，$5 \times 60\% = 3$ 人获奖。
• 你的代码：用 i (4) 来算，$4 \times 60\% = 2.4 \to 2$ 人获奖。
• 后果：计算出的获奖名额变少了，导致分数线偏高，答案错误。

修正：

int cnt = max(1, (i + 1) * w / 100); 

2. 编译错误：头文件写错

问题位置：

#include <bits/stdc++>

原因：少写了 .h。在本地或 OJ 上编译会直接报错。 修正：

#include <bits/stdc++.h>

3. 小瑕疵：输出格式

虽然大多数 OJ 对行末空格不敏感，但严格来说，你的写法会在最后一个数字后面多打印一个空格。

if(i <= n-1) { // 当 i 是最后一个时，这个条件依然成立
    cout << " "; 
}

建议写法：

cout << minscore << " "; // 简单粗暴，大部分题目都允许行末空格
// 或者更严谨：
cout << minscore;
if (i < n - 1) cout << " ";

---

修改后的正确代码

#include <bits/stdc++.h> // 修正1：头文件
using namespace std;

int main(){
    int n, w;
    cin >> n >> w;
    int score[605] = {0}; // 稍微开大一点点，防越界
    
    for(int i = 0; i < n; i++){
        int s;
        cin >> s;
        score[s]++;
        
        // 修正2：人数应该是 i + 1，不是 i
        int cnt = max(1, (i + 1) * w / 100);
        
        int minscore = 0;
        int man = 0;
        // 倒序寻找第 cnt 个人
        for(int j = 600; j >= 0; j--){
            man += score[j];
            if(man >= cnt){
                minscore = j;
                break;
            }
        }
        
        cout << minscore << " "; // 这样写通常没问题
    }
    return 0;
}

改掉人数计算那个 Bug，这道题就能拿满分了！

C++ :

#include<bits/stdc++.h>
using namespace std;
int t[605];
int n,w;
int main()
{
	int x;
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		t[x]++;
		int sum=0;
		for(int j=600;j>=0;j--)
		{
			sum+=t[j];
			if(sum>=max(1,i*w/100))
			{
				cout<<j<<' ';
				break;
			}
		}
	}
	return 0;
 }