题解：P14917 [GESP202512 五级] 数字移动

· · 题解

相较于第二题就水多了。

考虑到如果对于一个 x 进行若干次操作能够使得序列每个相同的数相邻，那么对于 x' \in (x ,10^5] 就可以用同 x 的操作来完成；如果一个 x 怎么操作都不能使得题目要求成立，那么 x' \in [0 ,x) 肯定都不行。

因此若 x 不符合题意，答案在 (x + 1 ,10^5] 之间。否则对于更大的 x 肯定都满足题意，答案在 [0 ,x) 间。

于是想到二分答案 x。

然后你动了若干次不超过 x 的数，贪心地，你不会让两个相同的数把另外一对相同的数隔开（比如 [a ,b ,b ,a] 肯定会操作为 [a ,a ,b ,b]，不劣地肯定是把能操作的数移动到序列的开头或者末尾。

因此剩下大于 x 的相对顺序肯定不会变。

比如 a = [1 ,2 ,1 ,3 ,2 ,3]，当 x = 1 时，删除 a_i \le 1 得到 [2 ,3 ,2 ,3]，这个就不合法，因为你动不了。

然而当 x = 2 时，剩下序列为 [3 ,3]，满足相同的数相邻，于是合法。

然后就做完了，时间复杂度为 \mathcal O(n\log V)。

哎真的没了嘛？不你还要特判 0，这也是为啥我写的是 [0 ,x) 而不是 [1 ,x)，但是好像数据没有答案为 0？

:::success[实现]

namespace lolcrying {

    inline bool check(int x){
        int cnt = 0 ;
        up(i ,1 ,n) if(a[i] > x) b[++ cnt] = a[i]; //记录剩余的数。
        up(i ,1 ,cnt) if(b[i] != b[i + 1] && b[i] != b[i - 1]) return 0; // 判断是否合法，如果不存在相邻的数与当前数相同肯定当前的 x 不合法。
        return 1; // 都满足则合法。
    } signed main(){

        n = read();
        up(i ,1 ,n) a[i] = read();

        int l = 1 ,r = 1e5 ,ans = 0;
         if(check(0)){ // 特判 ans = 0。
             puts("0") ; return 0; 
         }

        while(l <= r) {
            int mid = ((l + r) >> 1);
            if(check(mid)) r = mid - 1 ,ans = mid;
            else l = mid + 1;
        } writeln(ans);

        return 0 ;
    }

}

:::