问题描述

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如S = {1,2,2,2,3,5}。多重集S的众数是2，重数是3。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

输出输出示例

数据输入：第一行为多重集S中的元素个数n；在接下来的n行中，每行有一个自然数。
结果输出：第一行是众数，第二行是重数。

输入：

6
1
2
2
2
3
5

输出：

2
3

算法分析

这个问题其实很好理解而且暴力也不困难的，这里我用了分治的思想，首先先排序，然后取中间的数，往左往右遍历得到中间的数的个数和最优解进行比较。然后分别再取左边部分中间的数和右边部分中间的数，将大的集合分成小集合计算。当小集合中数的个数比最优解还小时就没必要进行比较了。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
int n, e[N], z, countz;

void fen(int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 1, x = e[mid];
    int ll = mid - 1, rr = mid + 1;
    while(e[ll] == x && ll) ll --;          //从中间往左查找和x相等的数
    while(e[rr] == x && rr <= n) rr ++;     //向右查找
    int le = rr - ll - 1;                   //中间数的个数
    if(le > countz || (le == countz && x < z)){
        countz = le;                        //如果个数一样，取最小的数 
        z = x;
    }
    if(ll - l + 1 >= countz) fen(l, ll);    //判断左边的段
    if(r - rr + 1 >= countz) fen(rr, r);    //判断右边的段

}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> e[i];
    sort(e + 1, e + n + 1);
    fen(1, n);
    cout << z << endl << countz;
    return 0;
}