数组：2.近序数组

【问题描述】

        对于一个具有 n 个元素的数组，如果可以将其分为两个部分，它的各个部分都是一个非严格有序数组，则我们称这样的数组为近序数组，例如

 数组 1、2、3、4、4、3、2、1是近序数组，数组 4、2、1、2、3、4也是近序数组，而1、5、7、3、9、3就不是近序数组，数组1、3、3、4是有序数组，是近序数组的特例。

 【输入形式】

        输入的第一行为一个整数n，表示数组的元素个数。

        接下来的一行，表示数组的元素。

【输出形式】

        如果给定的数组是近序数组输出Yes，否则输出No。
【样例输入1】

8
1 2 3 4 4 3 2 1

【样例输出1】

Yes

【样例输入2】

3 4 3 4

【样例输出2】

Yes

【样例输入3】

3 4 3 4 3

【样例输出3】

No

【样例说明】
【评分标准】

//给大家解读一下

上网也没找到近序数组的定义

个人认为近序数组就是由两个不一定相同单调性的区间构成的数组

记增区间为↑，减区间为↓，不增不减区间为=，若中间有两数相同为==

则近序数组可以为：

1.↑、↓、=（单纯一直增加，减小和不变的）

2.↑↓、↑=、↑==↓、↓↑、↓=、↓==↑、=↑、=↓

所以要分类讨论

代码如下：

#include//此题介绍一个近序数组的能分成两个非严格有序数组，可以转化为数组中有且仅有1或2个单调区间，即这个数组中只有1或0个转折点 
using namespace std;
int main() {
	int n,a,tp=100000,sum1,sum2,sum3,sum4,sum5,sum6;//tp为turning point转折点；此处tp初值设为100000是为了把tp和j区分开（因为测试点j和n不可能超过100000） 
	cin>>n;
	int arr[n];
	for(int i=0; i
		cin>>a;
		arr[i]=a;
	}
	if(arr[0]1]) { //第一种情况 ↑
		sum1=0;
		sum2=0;
		sum3=0;
		for(int j=1; j
			if(arr[j-1]>arr[j]) {
				tp=j;
				break;
			}
		}
		if(tp==100000) {
			cout<<"Yes"<
			return 0;//若无转折点，必为近序数组 
		}
		for(int k=tp; k-1; k++) {
			if(arr[k]>arr[k+1])
				sum1+=1;
			else
				break;
		}
		for(int k=tp; k-1; k++) {
			if(arr[k]1])
				sum2+=1;
			else
				break;
		}
		for(int k=tp; k-1; k++) {
			if(arr[k]==arr[k+1])
				sum3+=1;
			else
				break;
		}
		if(sum1==n-1-tp||sum2==n-1-tp||sum3==n-1-tp) {
			cout<<"Yes"<
		} else {
			cout<<"No"<
		}
	} else if(arr[0]>arr[1]) { //第二种情况 ↓
		sum1=0;
		sum2=0;
		sum3=0;
		for(int j=1; j
			if(arr[j-1]<=arr[j]) {
				tp=j;
				break;
			}
		}
		if(tp==100000) {
			cout<<"Yes"<
			return 0;
		}
		for(int k=tp; k-1; k++) {
			if(arr[k]1])
				sum1+=1;
			else
				break;
		}
		for(int k=tp; k-1; k++) {
			if(arr[k]>arr[k+1])
				sum2+=1;
			else
				break;
		}
		for(int k=tp; k-1; k++) {
			if(arr[k]==arr[k+1])
				sum3+=1;
			else
				break;
		}
		if(sum1==n-1-tp||sum2==n-1-tp||sum3==n-1-tp) {
			cout<<"Yes"<
		} else {
			cout<<"No"<
		}
	} else if(arr[0]=arr[1]) { //第三种情况 =
		sum1=0;
		sum2=0;
		sum3=0;
		sum4=0;
		sum5=0;
		sum6=0;
		for(int j=1; j-1; j++) {
			if(arr[j]1]) {
				sum1+=1;
			} else if(arr[j]>arr[j+1]) {
				sum2+=1;
			} else if(arr[j]==arr[j+1]) {
				sum3+=1;
			}
			for(int j=1; j
				if(arr[j-1]!=arr[j]) {
					tp=j;
					if(j==n-1) {
						cout<<"Yes"<
						return 0;
					} else {
						for(int k=tp; k-1; k++) {
							if(arr[k]1])
								sum4+=1;
							else
								break;
						}
						for(int k=tp; k-1; k++) {
							if(arr[k]>arr[k+1])
								sum5+=1;
							else
								break;
						}
						for(int k=tp; k-1; k++) {
							if(arr[k]==arr[k+1])
								sum6+=1;
							else
								break;
						}
					}
				}
			}
 
		}
		if(sum1==n-2||sum2==n-2||sum3==n-2||sum4==n-1-tp||sum5==n-1-tp||sum6==n-1-tp) {
			cout<<"Yes"<
		} else {
			cout<<"No"<
		}
	}
	system("pause");
	return 0;
}

PS：下午睡醒觉起来脑子坏掉了，用了个最笨的方法编了好长时间，就像打补丁一样改来改去，自己也不是很满意

uu们如果有更好更简洁的方法记得发我一下(>▽<)