首页 > 其他分享 >「CSP-J2020」 直播获奖 —— 桶排序例题

「CSP-J2020」 直播获奖 —— 桶排序例题

时间:2023-02-14 20:55:54浏览次数:58  
标签:600 int 样例 获奖 选手 100 例题 CSP J2020

(oh!多么美好的一天)

看题!

原题链接(洛谷)

[CSP-J2020] 直播获奖

题目描述

NOI2130 即将举行。为了增加观赏性,CCF 决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为 w%,即当前排名前 w% 的选手的最低成绩就是即时的分数线。

更具体地,若当前已评出了 p 个选手的成绩,则当前计划获奖人数为 \max(1, \lfloor p * w %\rfloor),其中 w 是获奖百分比,\lfloor x \rfloor 表示对 x 向下取整,\max(x,y) 表示 x 和 y 中较大的数。如有选手成绩相同,则所有成绩并列的选手都能获奖,因此实际获奖人数可能比计划中多。

作为评测组的技术人员,请你帮 CCF 写一个直播程序。

输入格式

第一行有两个整数 n, w。分别代表选手总数与获奖率。
第二行有 n 个整数,依次代表逐一评出的选手成绩。

输出格式

只有一行,包含 n 个非负整数,依次代表选手成绩逐一评出后,即时的获奖分数线。相邻两个整数间用一个空格分隔。

样例 #1

样例输入 #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

样例输入 #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 \sim 3 10
4 \sim 6 500
7 \sim 10 2000
11 \sim 17 10^4
18 \sim 20 10^5

对于所有测试点,每个选手的成绩均为不超过 600 的非负整数,获奖百分比 w 是一个正整数且 1 \le w \le 99。



分隔线



正文:

(为神马题目那么长)

OK,叕是一道简单的题
由于题目给的范围只有600,所以可以用:

桶排序!

桶排原理
所以:

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

完美!

标签:600,int,样例,获奖,选手,100,例题,CSP,J2020
From: https://www.cnblogs.com/momotrace/p/tong_pai_xu.html

相关文章

  • [CSP-S2019] Emiya 家今天的饭
    题解P5664这道题非常水,段誉初二就切了,但是我初中DP学的非常差,基本什么都不会,见到的小套路能会一个算一个吧。直接计算比较困难,尝试使用DP求出不合法的方案数即......
  • CSP NOIP 游记 2022
    CSP2022.9.17初赛前一天,++rp。今年flag:搞到7级钩子。2022.9.18CSP2022J1ACACBBBCADDACABFFFFFBFTTCCBTTTFCBAABCDAABCCACSP2022S1感觉考完非常不好。B......
  • [例题]一维前缀和
    [例题]一维前缀和#include<bits/stdc++.h>usingnamespacestd;intn,m;inta[100010];longlongper_sum[100010];intl,r;intmain(){ cin>>n>>m; for(inti......
  • CSP-J 2022 T2-解密
    原题目链接题目描述给定一个正整数\(k\),有\(k\)次询问,每次给定三个正整数\(n_i,e_i,d_i\),求两个正整数\(p_i,q_i\),使\(n_i=p_i\timesq_i\)、\(e_i\timesd......
  • CSP-J 2022 T1-乘方
    题目描述小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数\(a\)和\(b\),求\(a^b\)的值是多少。\(a^b\)即\(b\)个\(a\)相乘的值,例如\(2^3\)即......
  • P7074 [CSP-J 2020] 方格取数
    思路来自大佬:Indjy学校老师居然把这个题放在区间DP里面但是我没想到该怎样用,标签里也没有,那就用暴力DP来做吧。题目大意有一个\(n\timesm\)的方格,可以向下,向上,向右走......
  • 【CSP201312-4】有趣的数(数位DP)
    problem问题描述试题编号:201312-4试题名称:有趣的数时间限制:1.0s内存限制:256.0MB问题描述:问题描述我们把一个数称为有趣的,当且仅当:1.它的数字只包含0,......
  • 【CSP201803-1 】跳一跳,简单模拟
    problem试题编号:201803-1试题名称:跳一跳时间限制:1.0s内存限制:256.0MB问题描述:问题描述近来,跳一跳这款小游戏风靡全国,受到不少玩家的喜爱。简化后的跳一......
  • 【CSP201312-3】最大的矩形,单调栈
    problem201312-3试题名称:最大的矩形时间限制:1.0s内存限制:256.0MB问题描述:问题描述在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1≤i≤n)个矩形的高度......
  • 【CSP201312-2】ISBN号码,字符串,简单模拟
    problem试题编号:201312-2试题名称:ISBN号码时间限制:1.0s内存限制:256.0MB问题描述:问题描述每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、......