Codeforces Round 786 (Div. 3) D. A-B-C Sort

 D. A-B-C Sort

• 步骤 1 ：当 a不为空时，从 a中取出最后一个元素，并将其移动到数组 b的中间。如果 b 当前长度为奇数，则可以选择：将 a 中的元素放到 b 中间元素的左边或右边。结果， a 变空， b 由 n 个元素组成。
• 步骤 2 ：当 b不是空数组时，从 b 中取出中间的元素，移动到数组 c 的末尾。如果 b 当前长度为偶数，则可以从两个中间元素中选择一个。结果， b 变空， c 现在由 n 个元素组成。

 听起来很麻烦，但是通过模拟可知:

• a数组长度n为奇数时，那么a当中第一个元素必定是c数组当中的第一个元素
• 如果n为偶数时，那么取a头部两个元素的最小值为c元素的第一个元素 

那么我们遍历a数组只需要根据数组长度的变化更改取值同时更新a数组即可

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin >> T; while (T--)
#define LEN length()
#define all(a) a.begin(), a.end()
template <class T>
bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template <class T>
bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x & (-x))
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 7;
signed main()
{IOS
	use
	{
		int n;
		cin >> n;
		vct<int> a(n + 5, 1e9 + 7);
		int mins = 1e9 + 7;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			mmin(mins, a[i]);
		}
		bool isok = 1;
		if ((n % 2 && a[1] != mins) || (n % 2 == 0 && min(a[1], a[2]) != mins))
			no;
		else
		{
			if (n % 2)
			{
				int minx = a[1];
				int cnt = 0;
				for (int i = 2; i <= n; i++)
				{
					if (!cnt & 1)
					{
						if (min(a[i], a[i + 1]) < minx){isok = 0;break;}
						minx = min(a[i], a[i + 1]);
						a[i + 1] = max(a[i], a[i + 1]);
					}
					else
					{
						if (a[i] < minx){isok = 0;break;}
						minx = a[i];
					}
					cnt ^= 1;
				}
			}
			else
			{
				int minx = min(a[1], a[2]);
				int cnt = 1;
				a[2] = max(a[1], a[2]);
				for (int i = 2; i <= n; i++)
				{
					if (!cnt & 1)
					{
						if (min(a[i], a[i + 1]) < minx){isok = 0;break;}
						minx = min(a[i], a[i + 1]);
						a[i + 1] = max(a[i], a[i + 1]);
					}
					else
					{
						if (a[i] < minx){isok = 0;break;}
						minx = a[i];
					}
					cnt ^= 1;
				}
			}
			if (isok)yes;
			else no;
		}
	}
	return 0;
}