Min Max Sort

yemuzhe · 2023-01-26 22:07:53 · 题解

简化题意

• 给定一个长度为 n 的排列 p。
• 你可以进行若干次（可以 0 次）下面操作：
• • 首先选择两个不同的元素，记为 x, y，并将它们在 p 中删除。
  • 在 p 的开头插入 \min \{x, y\}，使其成为 p 中第一个元素。
  • 在 p 的最后插入 \max \{x, y\}，使其成为 p 中最后一个元素。
• 你的目标是通过最少的操作次数使得 p 变成升序的，即让 p = [1, 2, 3, \ldots, n]。
• 求这个最少的操作次数。

解题思路

观察到最后 p = [1, 2, 3, \ldots, n]，我们发现如果有至少 1 次操作则最后一次操作选的两个数一定是 1, n，因为最后时第一个数是 1，最后一个数是 n。

并且容易证明选择重复的数一定不比不选重复的数更优。以此类推，如果有至少 2 次操作则倒数第二次操作选的两个数一定是 2, n - 1，如果有至少 3 次操作则倒数第三次操作选的两个数一定是 3, n - 2……如果有至少 \big \lfloor \frac n 2 \big \rfloor 次操作则第一次操作为 \big \lfloor \frac n 2 \big \rfloor, n - \big \lfloor \frac n 2 \big \rfloor + 1。

例如样例的第四个字测试用例 p = [5, 2, 4, 1, 6, 3] 则是先选择 3, 4 使得 p = [3, 5, 2, 1, 6, 4]，再选择 2, 5 使得 p = [2, 3, 1, 6, 4, 5]，最后选择 1, 6 使得 p = [1, 2, 3, 4, 5, 6]，故答案为 3。如果 n 为奇数则不用管中间数。

但有时候答案不会取到 \big \lfloor \frac n 2 \big \rfloor。例如 p = [1, 3, 5, 6, 4, 2] 时，只要分别选择 2, 5 和 1, 6 即可，答案为 2；p = [2, 6, 3, 1, 4, 5] 时，只要选择 1, 6 即可，答案为1。

第一个例子是因为 3, 4 已经排好顺序，不用再动；第二个例子是因为 2, 3, 4, 5 已经排好顺序，不用再动。

记中间数 m = \big \lfloor \frac {n +1} 2 \big \rfloor。这启发我们找到一个最大的 k，若 n 为奇数，则满足 p _ {m - k}, p _ {m - k + 1}, \ldots p _ {m + k} 即最中间的 2k + 1 个数已经排好顺序；若 n 为偶数，则满足 p _ {m - k + 1}, p _ {m - k + 2}, \ldots, p _ {m + k} 即最中间的 2k 个数已经排好顺序。最终答案就是 \big \lfloor \frac n 2 \big \rfloor - k。

我们在找 k 时可以采用二分答案，二分域 \Big [0, \big \lfloor \frac n 2 \big \rfloor \Big]。确定区间 [l, r] 内几个数是否排好顺序的方法可以遍历一遍 p，若 p _ i = l 则 l 增加 1，最后查看 l 是否大于 r 即可。

时间复杂度：\text O (n \log n)。

AC Code

#include <cstdio>
#define N 200005
using namespace std;

int T, n, l, r, mid, a[N];

bool check (int x) // k = x 时中间的几个数是否已经排好序
{
    int l = (n + 1 >> 1) - x + (~n & 1), r = (n + 1 >> 1) + x;
    // 当 n 为奇数时，l = (n + 1) / 2 - x, r = (n + 1) / 2 + x
    // 当 n 为偶数时，l = (n + 1) / 2 - x + 1, r = (n + 1) / 2 + x
    for (int i = 1; i <= n; i ++) // 遍历数组
    {
        l += a[i] == l; // 如果 a[i] == l，则 l ++
    }
    return l > r; // 如果 l > r，则说明 l~r 这几个数都在数组中按顺序出现过，返回 true；否则返回 false
}

int main ()
{
    scanf ("%d", &T);
    while (T --)
    {
        scanf ("%d", &n);
        for (int i = 1; i <= n; i ++)
        {
            scanf ("%d", &a[i]);
        }
        l = 0, r = n >> 1; // 确定二分域
        while (l < r) // 开始二分
        {
            mid = l + r + 1 >> 1; // 中间数取 (l + r + 1) / 2，如果不加 1 可能会死循环
            if (check (mid)) // 如果 k = mid 可以
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        printf ("%d\n", (n >> 1) - l); // 答案为 n / 2 - k
    }
    return 0;
}