自动搬运

查看原文

来自洛谷，原作者为

	Khassar **

搬运于2025-08-24 21:58:18，当前版本为作者最后更新于2018-03-07 10:28:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这个题嘛，总的来说还是比较水的吧，签到题吧，我交的大家几乎都是1A，但题解却空空的岂不是不好。

首先$n\geq 100000$（诶!好像是$=$），$a_i\leq 10^9$，这告诉我们直接开桶和$n^2$枚举是不可以的。

他还没告诉我$T$是多少（可能是我瞎，没看见），但根据我的评测结果经验$T$是不大的。

所以我有一个大胆的想法：我们先把$a_i$都读进来，然后排个序，这样一样的票都聚在了一起，而且$a_i$还是从小到大排好了的，方便输出。
因为一样的票都聚在了一起统计各种票都出现了几次只需要$O(n)$的扫一遍就可以了（具体实现可以看代码），这样总时间复杂度是$O(Tnlogn)$的，所以我觉的如果给我一个大点的$T$就GG了。对于输出$-1$的特殊情况，我们可以同时在$O(n)$遍历时一并记一下。

当然我的码风对除我以外的人都不太友好。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>
#include<set>

#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memcpy((a),(b),sizeof((b)))
#define D double

using namespace std;

const int N=100005;

int T,a[N],ans[N],cnt,s,n;//ans用来存答案

IL int read() {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
	return x*f;
}
IL void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

signed main()
{
	T=read();
	while(T--) {
		s=0;cnt=0;//s记录出现过多少种票，cnt记录答案的数量
		n=read();
		Rf(i,1,n) a[i]=read();
		sort(a+1,a+1+n);a[n+1]=0;//把第n+1个赋成0强制与第n个不一样，方便一个for处理完
		R int sum=1,mx=0;//sum记录一种票已经出现过多少次,mx记录出现过的最大次数
		Rf(i,2,n+1) {//枚举到n+1，一次处理完，不用在最后再判一次
			if(a[i]!=a[i-1]) {//和前一个不一样，就是又出现了一个新的
				s++;
				if(sum>mx) {//比已知的票数最大值还要大就更新
					mx=sum;
					ans[cnt=1]=a[i-1];
				}
				else if(sum==mx) {//如果一样就会多一个答案
					ans[++cnt]=a[i-1];
				}
				sum=1;//重置计数器
			}else sum++;//否则计数器+1
		}
		if(s==cnt) {//特殊情况
			puts("-1");
			continue;
		}
		write(cnt);putchar('\n');
		Rf(i,1,cnt) {
			write(ans[i]);putchar(' ');
		}
		puts("");
	}

	return 0;
}