CF451B

标签：typedef ch const CF451B int 50 数组

题目简化和分析：

这题就是判断将一段翻转后是否能变为升序的数组。

我的方法是保存原数组每一个数出现的位置（相同任意一个），让后另外用一个数组存储排好序后的原数组，逐一进行比较。

• 若同，则跳到下一个元素比较继续。
• 若不同，枚举当前位置到排序数组当前元素在原数组中的位置，时候一直为降序。
• 若多次出现不同，则跳出循环，立即输出。
• 特别的，若一直相同任意输出相同的左端点和右端点，但保证是合法范围内的。

Solution:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N=1e5+50;
const int M=1e5+50;
const int Mod=1e9+7;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n;
int a[N],b[N];

map<int,int>pos;

int main()
{
	n=read();
	for(int i=1;i<=n;++i) a[i]=read(),b[i]=a[i],pos[a[i]]=i;
	sort(b+1,b+n+1);
	int l=0,r=0;
	bool flag=1;
	for(int i=1;i<=n;){
		if(a[i]==b[i]){
			i++;
			continue;
		}
		if(l!=0){
			flag=0;
			break;
		}else{
			l=i,r=pos[b[i]];
			i=pos[b[i]]+1;
			for(int j=l;j<r;++j){
				if(a[j]<a[j+1]){
					flag=0;
					break;
				}
			}
			if(!flag) break;
		}
	}
	if(flag){
		printf("yes\n");
		if(l==0) l=r=1;
		printf("%d %d\n",l,r);
	}else{
		printf("no\n");
	}
	return 0;
}

标签：typedef,ch,const,CF451B,int,50,数组
From： https://www.cnblogs.com/R-V-G/p/16594478.html