题解 | 小苯的麦克斯

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//取两个数字的MEX
const int getMEX(const int& a, const int& b) {
    for (int i = 0;  ; i++) {
        if ((a != i) && (b != i)) {
            return i;
        }
    }
}

int main() {

    //数据组数
    int T = 0;
    cin >> T;

    //二维数组，用于存储所有输入
    vector<vector<int>>input;

    for (int i = 0; i < T; i++) {
        int n = 0;
        cin >> n;
        vector<int>group;
        for (int j = 0; j < n; j++) {
            int a = 0;
            cin >> a;
            group.push_back(a);
        }
        input.push_back(group);
    }

    //答案寄存器
    vector<int>answers(T);

    //要求MAX-MEX最大，要尽可能让MAX更大且MEX更小
    //选取的区间应该尽可能包含序列的最大值且避免包含太小的非负整数
    //理想的情况是只选出一个最大值，但要求不能只选一个数字
    //考虑只选择两个数字

    for (int i = 0; i < T;  i++) {
        int size = input[i].size();
        if (size < 2) {
            //输入数据有问题，一个序列少于两个
            continue;
        }
        int MAX = max(input[i][0], input[i][1]);
        int MEX = getMEX(input[i][0], input[i][1]);
        answers[i] = MAX - MEX;
        for (int j = 2; j < size; j++) {
            MAX = max(input[i][j - 1], input[i][j]);
            MEX = getMEX(input[i][j - 1], input[i][j]);
            int difference = MAX - MEX;
            if (difference > answers[i]) {
                answers[i] = difference;
            }
        }
    }

    //输出
    for (int i = 0; i < T; i++) {
        cout << answers[i] << endl;
    }

}
// 64 位输出请用 printf("%lld")