欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客网暑期ACM多校训练营(第四场)G.Maximum Mode (思维)

程序员文章站 2022-04-02 22:09:14
...

题目链接

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

The mode of an integer sequence is the value that appears most often. Chiaki has n integers a1,a2,...,an. She woud like to delete exactly m of them such that: the rest integers have only one mode and the mode is maximum.

输入描述:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m < n) -- the length of the sequence and the number of integers to delete.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) denoting the sequence.
It is guaranteed that the sum of all n does not exceed 106.

输出描述:

For each test case, output an integer denoting the only maximum mode, or -1 if Chiaki cannot achieve it.

示例1

输入

5
5 0
2 2 3 3 4
5 1
2 2 3 3 4
5 2
2 2 3 3 4
5 3
2 2 3 3 4
5 4
2 2 3 3 4

输出

-1
3
3
3
4

题意:一共T组样例,对于每组样例给出一行N和M,分别表示随后一行有N个数和需要删去的数的数量为M.且要求删除M个数后该数列中的众数唯一且最大,否则输出-1.

题解:我们只需要从大到小枚举每种给出的数,判断枚举的该数在删除M个数后,能否成为该数列中的唯一众数(即将所有个数大于等于它的都减到小于它的最小值s是否小于等于M),若是直接break即可,否则找不到可行解输出-1.(最大的坑点就是题目的T没有给出范围,只知道T组样例中N的总和不超过1e6,出题人故意出了多样例的情况卡掉了memset,因此在对数组初始化时无法使用memset,只能考虑使用其他办法来实现,我是通过map将数据进行hash小的,做法不唯一).

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
map<int, int>ins; 
struct node {
	int x;
	int cnt;
}a[maxn];
struct SUM {
	int cnt;
	int sum;
}b[maxn];
bool cmp(node x, node y) {         //按照x从大到小排序
	return x.x > y.x;
}
bool cmp2(SUM x, SUM y) {          //按照cnt从大到小排序
	return x.cnt > y.cnt;
}
int n, m, top, top2;
bool ok(int i) {                   //判断删除m个时,当前值x是能成为唯一众数
	int s = b[i].sum - 1;
	if (m >= s) return true;
	return false;
}
void input() {
	int x;
	ins.clear();                   //清空ins,以便记录某x值是否出现
	top = 1;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		if (!ins[x]) {
			ins[x] = top;
			a[top].x = x;
			a[top++].cnt = 1;
		}
		else
			a[ins[x]].cnt++;
	}
	sort(a + 1, a + top, cmp);      //按照x从大到小排序(注意是a+top)
}
void solve() {
	ins.clear();                    //清空ins,以便记录某cnt次是否出现
	top2 = 1;
	for (int i = 1; i < top; i++) {
		int cnt = a[i].cnt;
		if (!ins[cnt]) {
			ins[cnt] = top2;
			b[top2].cnt = cnt;
			b[top2++].sum = 1;      //此时的sum记录的是个数
		}
		else
			b[ins[cnt]].sum++;
	}
	sort(b + 1, b + top2, cmp2);    //按照cnt从大到小排序(注意是b+top2)
	int count = b[1].sum;           //count记录大于等于b[i].cnt的种类总数
	ins[b[1].cnt] = 1;
	for (int i = 2; i < top2; i++) {//此时的sum-1记录的是使b[i].cnt中的一种x成为众数最少需要减的个数
		int tt = b[i].sum;          //tt先保存下当前b[i].cnt种类的个数
		b[i].sum += b[i - 1].sum + count*(b[i - 1].cnt - b[i].cnt);
		count += tt;                
		ins[b[i].cnt] = i;          //修改ins值,方便后面索引
	}
}
void output() {                     //输出
	int i;
	for (i = 1; i < top; i++)
		if (ok(ins[a[i].cnt]))	
			break;
	if (i < top) 
		printf("%d\n", a[i].x);
	else 
		printf("-1\n");
}
int main(){
	int t;
	scanf("%d", &t);
	while (t--) {
		input();
		solve();
		output();	
	}
	return 0;
}

这题本来不想发的,为了加深犯错的记忆(TLE了好几次才知道是memset的问题,后来又因为sort的上界范围写多1了,在没有初始化的情况下刚好会被卡掉wa了几发,衰~)