问题描述

却说天下大乱，曹操挟天子以令诸侯，招募了 n 员猛将，想要兴兵南下。为了联络方便，每位武将都会驻扎在一个城池中，用 aiai​ 表示第 i 个武将驻扎的城池编号。

这一日，曹操看着账下的武将名单，不禁陷入了沉思。他摸着胡子，对身边的谋士郭嘉说道：“奉孝啊，你看这名单上的武将，个个都是能征善战之辈，但你也知道，这军中之事，最忌讳的就是结党营私。你看这名单上，有些人住在一个城池里，这要是都带上了，难免会…”

郭嘉听罢，立刻明白了曹操的担忧。他微微一笑，说道：“主公英明！这挑选武将，确实要慎重啊！不如这样，我给主公精挑细选 kk 员猛将，让他们尽量避免来自同一城池，以免生出不必要的麻烦。主公意下如何？”

曹操听后龙颜大悦，说道：“妙啊！那你快帮我算算，挑选的 kk 员猛将，最多能有几个是单独来自一个城池的？”

输入格式

第一行输入两个整数 n,k（1≤k≤n≤105），表示武将的总数量和要挑选的武将数量。

第二行输入 n 个整数 a1,a2,…,an（1≤ai​≤105），表示每位武将驻扎的城池编号。

输出格式

输出一个整数，表示最多能挑选的单独来自不同城池的猛将数量。

样例输入

5 4
1 1 2 2 3

样例输出

2

样例说明

武将的驻扎城池编号分别为 11、11、22、22 和 33。可挑选 22 个来自城池 11 的的武将，11 个来自城池 22 的武将，以及 11 个来自城池 33 的武将。这样，单独来自一个城池的武将共有 22 个。

运行限制

原文链接：1.挑选武将【算法赛】 - 蓝桥云课https://www.lanqiao.cn/problems/19784/learning/?page=1&first_category_id=1 

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int a[N],b[N],c=0;
int main(){
	int n=0,k=0;cin>>n>>k;
	for (int i=0;i<n;i++) {
		cin>>a[i];
		if (b[a[i]]==0) b[a[i]]=1,c++;
		else ++b[a[i]];
	}
	sort(b,b+N,[](int x,int y) {return x>y;});
	if (c>=k) cout<<k<<"\n";
	else {
		for (int r=k-c,i=0;r>0;i++,c--) r-=b[i]-1;
		cout<<c<<"\n";
	}
	
}

 提交通过