CF1674D-A-B-C Sort

2022-05-03 题解

题目大意：给定一个数组a，每次将a的最后一项插入另一个数组b的中间（如果数组b有奇数个元素，可以任意选择插入到中间元素的左边或者右边）。之后每次将数组b的中间元素放到数组c的尾部（如果数组b中有偶数个元素，可以任意选择靠左或者靠右的元素）。问最终是否能使得到的c数组不下降。

若a中有奇数个元素，a的第一项一定是最后一个进入b数组，且第一个进入c数组的，所以a最左边的元素一定要是a中最小的；若a中有偶数个元素，a中的第一跟第二个元素肯定是最后两个进入b，最先两个进入c的元素，且可以调换顺序。也就是说，如果a中有偶数个元素，第一个或者第二个元素一定要是最小的。

处理完的前缀就不用考虑了，所以a中元素个数总是在奇数与偶数间转换的。一直处理下去就行了。

#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005];
int main()
{
    int _, i, n;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%d", &n);
        for (i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        sort(a + 1, a + 1 + n);
        int ar = n & 1;//剩余元素个数是/否为奇数
        for (i = 1; i <= n; i++, ar ^= 1)
        {
//由分析可得出，可等效认为需要当前元素在a的后缀中最小，且当数组长度为偶数时，第一个元素与第二个元素可交换
            if (!ar && b[i] > b[i + 1])
                swap(b[i], b[i + 1]);
            int t = lower_bound(a + 1, a + 1 + n, b[i]) - a;
            if (t > i)
                break;
        }
        if (i <= n)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}