自动搬运

查看原文

来自洛谷，原作者为

	Light_Star_RPmax_AFO 踏破千山去，直上九重天

搬运于2025-08-24 22:44:53，当前版本为作者最后更新于2023-02-15 17:34:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题目传送

题目

[PA2021] Koszulki

题目描述

$n$ 个人参加一场比赛，其中第 $i$ 个人的得分为 $a_i$。

主办方决定至少颁发 $k$ 件礼物。

但是，若 $\exist 1 \leq x < y \leq n, a_x \geq a_y$ 且 $x$ 未拿到礼物但 $y$ 拿到礼物，$x$ 会不满意。

主办方希望每个人都满意，求颁发的礼物数量的最小值。

贪心

一道红题

这题肯定要先满足高分先发，所以我们就用 桶排序 ，这样我们就可以记录每个分数有多少人。

为了让礼物数最少，我们就在比 $k$ 高的时候直接输出就可以了

#include<bits/stdc++.h>
using namespace std;
map<int,int>a;//桶。
int main(){
	int a[10010],x;
	int n,ans=0,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>x,a[x]++;
	for(int i=120;i>=0;i--){
		ans+=a[i];
		if(ans>=k){cout<<ans;return 0;}
	}
}