python/TangDou/LanQiaoBei/LanQiao14ShengSai/5.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
unordered_set<int> _set;
/*
4
1 3 4 2

答案：
2 2 3
*/
int cnt;
int main() {
    // freopen("5.in", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];

        b[a[i]]++;         // 记录每个数字的个数
        _set.insert(a[i]); // 记录整体的数字个数
    }

    sort(a, a + n); // 从小到大排序

    int cnt = 0;
    while (true) {
        // 找到次小值
        cnt++;
        int cx = upper_bound(a, a + n, a[0]) - a;
        // 最右侧最小位置
        int zx = cx - 1;
        // 最小少了一个，次小多了一个
        b[a[zx]]--, b[a[cx]]++;
        if (b[a[zx]] == 0) _set.erase(a[zx]);
        // 最右侧最小修改为次小
        a[zx] = a[cx];
        if (_set.size() < 3) break;

        // 找出最大值的左边界
        cnt++;
        int zd = lower_bound(a, a + n, a[n - 1]) - a;
        // 次大位置
        int cd = zd - 1;

        // 最大少了一个，次大多了一个
        b[a[zd]]--, b[a[cd]]++;
        if (b[a[zd]] == 0) _set.erase(a[zd]);
        // 将最左侧最大修改为次大
        a[zd] = a[cd];

        if (_set.size() < 3) break;
    }

    // 输出执行次数
    cout << cnt << " ";

    // 利用桶找出最小值
    for (int i = 0; i < n; i++)
        if (b[i]) {
            cout << i << " ";
            break;
        }
    // 利用桶找出最大值
    for (int i = n - 1; i >= 0; i--)
        if (b[i]) {
            cout << i << " ";
            break;
        }
    return 0;
}