G5019 [GESP202512 五级] 数字移动 题解

知识点：二分答案、序列扫描、配对。

解题思路

二分最终剩余数字的最大允许值limit，扫描所有大于limit的元素，要求它们按原顺序能两两配成相同值；忽略较小元素。

为什么正确

必须被移除的大元素不能留到最后，能消除它们的必要充分条件是扫描配对无冲突且无剩余；提高limit只会放松限制。

易错点

配对保持大元素原顺序，不可先排序；最后pending必须为空。

复杂度

时间O(n log A)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    auto ok=[&](int limit) {
        int pending=-1;
        for(int x:a)if(x>limit) {
            if(pending==-1)pending=x;
            else {
                if(pending!=x)return false;
                pending=-1;
            }
        }
        return pending==-1;
    }
    ;
    int lo=0,hi=100000;
    while(lo<hi) {
        int m=(lo+hi)/2;
        if(ok(m))hi=m;
        else lo=m+1;
    }
    cout<<lo;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。