PDF文档公众号回复关键字:20240928
1 2020 CSP-J 题目1 优秀的拆分
[题目描述]
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线
更具体地，若当前已评出了 p个选手的成绩，则当前计划获奖人数为 max(1,⌊p×w%⌋)，其中 w 是获奖百分比，⌊x⌋ 表示对 x 向下取整，max(x,y) 表示 x 和 y中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多
[输入格式]
第一行有两个整数 n,w。分别代表选手总数与获奖率
第二行有 n个整数，依次代表逐一评出的选手成绩
[输出格式]
只有一行，包含 n个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔
[输入输出样例]
输入 #1
10 60
200 300 400 500 600 600 0 300 200 100
输出 #1
200 300 400 400 400 500 400 400 300 300
输入 #2
10 30
100 100 600 100 100 100 100 100 100 100
输出 #2
100 100 600 600 600 600 100 100 100 100
说明/提示
样例 1 说明
各测试点的 n 如下表：
| 测试点编号 | n= |
|---|---|
| 1∼3 | 10 |
| 4∼6 | 500 |
| 7∼10 | 2000 |
| 11∼17 | 10^4 |
| 18∼20 | 10^5 |
对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，获奖百分比 w 是一个正整数且 1≤w≤99
2 相关知识点
1) 向下取整
数学符号
⌊x⌋ 向下取整符号 表示小于等于 x 的最大的整数
例如
⌊13/3⌋=4
⌈x⌉ 向上取整符号 表示大于等于 x 的最小的整数
例如
⌈13/3⌉=5
整数除法
整数除法默认向下取整
例如 5/2=2
#include<bits/stdc++.h>
using namespace std;
/*
2个整数相除结果也是整数，如果不能整除会向下取整
*/
int main(){
int a=15,b=2;
int c=15/2;
cout<<"15/2为:"<<c<<endl;
return 0;
}
/*
输出:
15/2为:7
*/
2) max 最大值
在 C++ 标准库中，max 函数用于比较两个值并返回较大的那个值。它的定义位于头文件
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
// 示例1：比较两个整数
int num1 = 1, num2 = 19;
int maxInt = std::max(num1, num2);
cout << "Max of " << num1 << " and " << num2 << ": " << maxInt << endl;
// 示例2：比较两个浮点数
double num3 = 9.6, num4 = 9.7;
double maxDouble = std::max(num3, num4);
cout << "Max of " << num3 << " and " << num4 << ": " << maxDouble << endl;
// 示例3：比较字符 a的ASCII码为99 A的ASCII码为67 所以a大
char char1 = 'c', char2 = 'C';
char maxChar = std::max(char1, char2);
cout << "Max of " << char1 << " and " << char2 << ": " << maxChar << endl;
return 0;
}
/**
Max of 1 and 19: 19
Max of 9.6 and 9.7: 9.7
Max of c and C: c
*/
3) 计数排序
计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于整数排序且待排序的元素范围相对较小的情况。它的基本思想是通过统计每个元素出现的次数，然后根据统计信息将元素放回原数组的正确位置，从而实现排序
例题
如下几个数字进行计数排序
5 6 8 3 2 4
声明数组a[10]={0},分别把上面数字作为a数字下标，值为当前数+1
赋值后数组如下
下标 0 1 2 3 4 5 6 7 8 9
数值 0 0 1 1 1 1 1 0 1 0
逐一输出不为0的数的下标，如果值大于1，输出多次
计数排序，是对哈希直接定址法的变形应用,具体思路为:统计相同元素出现次数,根据统计的结果将序列回收到原来的序列中
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]={3,4,2,7,5,4,3,3,3,5};
int cnt[7]={0};//cnt数组记录对应下标出现次数
for(int i=0;i<10;i++){
cnt[a[i]]++;
}
for(int i=0;i<=7;i++){//枚举对应范围的数 从最小到最大，本示例从0~7即可
while(cnt[i]>0){//一个数字出现多次时，cnt[i]为对应的数为出现几次
cout<<i<<" ";
cnt[i]--;
}
}
return 0;
}
/*
输出
2 3 3 3 3 4 4 5 5 7
*/
3 思路分析
每录入一个学生成绩，使用计数排序存储到数组中，对到目前为止成绩进行排序
从高到低计算获奖人数，直到满额位置
#include<bits/stdc++.h>
using namespace std;
/*
s[605] 每个选手成绩有几个人
s[200]=2 表示成绩为200的有2人
n选手总数 w获奖率
pcnt 获奖人数
score 选手成绩
tot 统计获奖学生数
pos 成绩从高到低记录当前获奖学生成绩位置
*/
int s[605],n,w,pcnt,score,tot,pos;
int main(){
cin>>n>>w;//输入选手人数 和获奖率
for(int i=1;i<=n;i++){//前i个选手
pcnt=max(1,i*w/100);//i个选手的获奖人数
cin>>score;//第i个选手的分数
s[score]++;//把第i个选手分数作为计数排序下标 值表示有几个人
tot=0,pos=601;
while(tot<pcnt){//循环选够sz个人，找到最低分数可能多个超过计算获奖人数sz
pos--;//s数组位置减1，s[i]成绩的位置，找前1个
tot+=s[pos];//累加s[i]成绩获奖人数
}
cout<<pos<<" ";//刚好找满获将人数的位置，或者此成绩比较多，加上此位置成绩人数刚好超过获奖人数
}
return 0;
}