#include <iostream>
#include <algorithm>
using namespace std;
int n,w;
int a[100010];

bool cmp(int x, int y){
   return x>y;
}

int main(){
    cin>>n>>w;
    for (int i = 1; i <=n; i++){
        cin>>a[i];
        sort(a+1,a+1+i,cmp);
        int p=max(1,i*w/100);
        cout<<a[p]<<" ";
    }
    return 0;
}

方法二：桶排序，满分

代码分析：

输入部分：
- 通过cin >> n >> w读取选手的总数n和获奖率w%。
- 然后逐一读取每个选手的成绩x，并更新数组a[x]，即a[x]++表示当前得x分的选手数加1。
获奖人数计算：
- 对于第i个选手评出后，计划获奖人数为p = max(1, i * w / 100)，即根据当前已评出的选手数量i和获奖率w计算计划获奖人数。需要注意的是，获奖人数最少为1（即使是第一个选手也要有一个获奖）。
即时获奖分数线的确定：
- 从最高分600分开始，逐一向下检查每个分数段的选手数量，累计已获奖的选手人数sum。如果累加的总人数达到计划的获奖人数p，当前的分数就是当前即时的获奖分数线。
输出部分：
- 每次找到当前分数线后输出分数j，并在所有n个选手的成绩评出后，输出一行由n个即时分数线构成的结果。

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

int n, w;         // n表示选手总数，w表示获奖率（百分比）
int a[1010];      // a[i]表示得i分的选手有多少个，初始化为0，数组大小设置为1010是为了覆盖到所有可能的成绩范围。

int main() {
    cin >> n >> w;  // 输入选手总数n和获奖率w
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;  // 输入每个选手的成绩
        a[x]++;    // 将得分x的选手数量加1，记录当前成绩的分布情况
        
        // 计算当前的计划获奖人数
        int p = max(1, i * w / 100);  // p表示当前计划获奖人数，需取不小于1的整数
        
        int sum = 0;  // 累计获奖人数
        // 从高分到低分，依次计算累加总的获奖人数
        for (int j = 600; j >= 0; j--) {  // 题目中可能的最大分数为600，因此从600开始向下遍历
            if (sum + a[j] >= p) {  // 若当前累计人数加上得分为j的选手数已经达到或超过计划获奖人数
                cout << j << " ";   // 输出当前获奖分数线（即j分）
                break;              // 找到即时获奖分数线后跳出循环
            }
            sum += a[j];  // 累加得分为j的选手数，继续往下检查较低的分数
        }
    }
    
    return 0;
}

Previous Topic

Back to Lesson

Next Topic