P9044 [PA2021] Koszulki 题解
Light_Star_RPmax_AFO
·
·
题解
前言
题目传送
题目
[PA2021] Koszulki
题目描述
主办方决定至少颁发 $k$ 件礼物。
但是，若 $\exist 1 \leq x < y \leq n, a_x \geq a_y$ 且 $x$ 未拿到礼物但 $y$ 拿到礼物，$x$ 会不满意。
主办方希望每个人都满意，求颁发的礼物数量的最小值。
# 贪心
一道红题
这题肯定要先满足高分先发，所以我们就用 **桶排序** ，这样我们就可以记录每个分数有多少人。
为了让礼物数最少，我们就在比 $k$ 高的时候直接输出就可以了
```cpp
#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;}
}
}
```