塔子哥的美食节-阿里淘天2024笔试(codefun2000)

题目链接
塔子哥的美食节-阿里淘天2024笔试(codefun2000)

题目内容

塔子哥是一位美食评论家，他最近参加了一个美食节，品尝了 n 种不同的美食，每种美食都有一个特定的人气值。现在，塔子哥想写一篇关于这次美食节的文章，他打算挑选出 k 种美食，使得文章中能够突出一种特别受欢迎的美食。为了增加文章的吸引力，他希望选择的美食中，有一种美食的人气值能够尽可能高。

输入描述

本题有多组测试数据。
第一行一个正整数 T，表示数据的组数。
接下来，对于每组测试数据，输入包含两行：
第一行两个正整数 n 和 k，表示美食的种类数和塔子哥需要挑选的美食数量。
第二行 n 个正整数，每个数表示一种美食的人气值。

输出描述

输出包含 T 行，对于每个测试数据：
每行一个正整数，表示选出 k 种美食组成的新美食列表中出现次数最多的美食的最大人气值。

样例1

输入

1
6 3
2 2 2 1 1 1

输出

2

提示

1≤T≤100
1 ≤ k ≤ n ≤ 1 0 5 1≤k≤n≤10^5 1≤k≤n≤105
1 ≤ a i ≤ 1 0 9 1≤ai≤10^9 1≤ai≤109

题解1

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int t, n, k, a[N];
unordered_map<int,int> hmap;

bool cmp(int a, int b){
	return a > b;
}

int main(){
	scanf("%d", &t);
	while(t--){
		hmap.clear();
		scanf("%d%d", &n, &k);
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if(hmap.count(a[i]) == 0) hmap[a[i]] = 1;
			else hmap[a[i]]++;
		}
		sort(a + 1, a + n + 1, cmp); // 优先选择人气值高的美食 
		n = unique(a + 1, a + n + 1) - a - 1; // 对排序后的数组进行去重 
		
		int ans = 0;
		while(k){
			ans = 0;
			for(int i = 1; i <= n && k; i++){
				if(hmap[a[i]]) {
					ans = max(ans, a[i]);
					k--;
					hmap[a[i]]--;
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}