A. Prof. Slim

题目

给定一个包含 n 个整数 a1,a2,…,an 的数组，其中 ai≠0，检查您是否可以通过使用以下操作任意次数（可能为零）对该数组进行排序。如果数组的元素以非递减顺序排列，则数组已排序。

选择两个索引 i 和 j (1≤i,j≤n) 使得 ai 和 aj 具有不同的符号。换句话说，一个必须是正面的，一个必须是负面的。
交换 ai 和 aj 的符号。例如，如果您选择 ai=3 和 aj=-2，那么它们将变为 ai=-3 和 aj=2。

输入
第一行包含一个整数 t (1≤t≤104)——测试用例的数量。然后是 t 个测试用例。

每个测试用例的第一行包含一个整数 n (1≤n≤105) — 数组 a 的长度。

下一行包含 n 个整数 a1,a2,…,an (−109≤ai≤109, ai≠0)，由描述数组 a 的元素的空格分隔。

保证所有测试用例的 n 总和不超过 105。

输出
对于每个测试用例，如果数组可以按非递减顺序排序，则打印“YES”，否则打印“NO”。您可以在任何情况下打印每个字母（大写或小写）

样例

input

4
7
7 3 2 -11 -13 -17 -23
6
4 10 25 47 71 96
6
71 -35 7 -4 -11 -25
6
-45 9 -48 -67 -55 7

output

NO
YES
YES
NO

思路：统计负数的个数，因为负数的个数等于左边绝对值递减的个数

这样就可以分别实现左边判绝对值递减，右边判绝对值递增

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int a[N];

void slove()
{
		int n;
		cin >> n;
		int cnt = 0; //统计负号个数
		for(int i=0; i<n; i++)
		{
			cin >> a[i];
			if(a[i] < 0)
			{
				cnt ++;
				a[i] = -a[i];
			} 
		}
		//判断递减情况
		for(int i=0; i<cnt-1; i++)
		{
			if(a[i+1] - a[i] > 0)
			{
				printf("NO\n");
				return ;
			}
			
		}
		//递增情况
		for(int i=cnt; i<n-1; i++)
		{
			if(a[i+1] - a[i] < 0)
			{
				printf("NO\n");
				return ;
			}
		}
		printf("YES\n");
}

int main()
{
	int T;
	cin >> T;
	while(T --)
	{
		slove();
	}
	return 0;
}