题解 P4263 【[Code+#3]投票统计】

· · 题解

这个题嘛，总的来说还是比较水的吧，签到题吧，我交的大家几乎都是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;
}