ACM模版

描述

题解

很有趣的一道题，不算难，但是和几个朋友讨论这道题涨了些许姿势~~~

首先，这道题如果用 map 写，理论上会超时，本来这样就是小题大做。比较直观的是 sort 一下，然后扫描一下就好了，但是如果只是这样也就没有讨论的必要了，试图寻找更好的解题思路时，我的思维过于局限，局限在了计数上，当然并不是说计数就无法更优，只是我没有参透些许。

经过讨论，有四种不错的思路：
第一种，多重 HASH 搞；
第二种，不断从数组中取数对，每次都取不同的两个数，直到无法再取，那么剩下的就是答案；
第三种，其实这个问题转换一下就是求第 K 大数的问题，不过这里的 K 等于 (n + 1) / 2，解题思路和快排相似；
第四种，也是我所给出的代码，虽然我一直执着于计数，感觉计数很难实现更快的解法，但是这个解法依然是计数，效率却高了很多，是 O(N)，具体思维也就是缩放计数，原题因为数据范围为1e9太大无法开数组计数，导致复杂度难以降低，就着这个思维，如何将其缩小，以满足可以开数组计数，其实这里可以理解为将高位和低位拆解开，高位的先计数，然后从满足高位计数条件的结果中进行低位的计数，最后选取低位计数中的符合要求的结果即可，还有略微的优化空间，但是思路十分不错，还是我的道行太低！！！

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

#define MAXN 10000005
#define BASE 1000

using namespace std;

int A[MAXN];
int cnt[MAXN / 10];
int deep[BASE + 10];

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        memset(cnt, 0, sizeof(cnt));
        memset(deep, 0, sizeof(deep));

        int n, a, b, res = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", A + i);
            b = A[i] / BASE;
            cnt[b]++;
            res = (cnt[res] < cnt[b]) ? b : res;
        }

        int g = 0;
        for (int i = 0; i < n; i++)
        {
            if (A[i] / BASE == res)
            {
                a = A[i] % BASE;
                deep[a]++;
                g = (deep[g] < deep[a]) ? a : g;
            }
        }
        printf("%d\n", g + res * 1000);
    }

    return 0;
}