/*
思路：
找到单调下降串的起始位置[l, r]
如果左边 0...l-1中的最大值 > l...r中的最小值 或者
r+1...n中的最小值 < l...r中的最大值 都是不能实现排序的！
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
int cur, nt;
int cnt;
int num[100005];
int main(){
int i, n;
int begin, end;
int flag;
int min1, max2;
while(scanf("%d", &n)!=EOF){
cnt=cur=0;
flag=0;
for(i=1; i<=n; ++i){
scanf("%d", &nt);
num[i]=nt;
if(nt>cur)
flag=0;
if(!flag && nt<cur){
++cnt;
flag=1;
begin=i-1;
end=i;
}
if(flag && nt<cur)
end=i;
cur=nt;
}
if(cnt==1){
min1=0x3f3f3f3f;
if(end!=n)
min1=num[end+1];
max2=-0x3f3f3f3f;
if(begin!=1)
max2=num[begin-1];
if(max2>num[end] || min1<num[begin])
printf("no\n");
else
printf("yes\n%d %d\n", begin, end);
}
else if(cnt==0)
printf("yes\n1 1\n");
else printf("no\n");
}
return 0;
}
/*
思路：
将两边单调递增的序列排除（将元素和元素下标一一映射起来，排序之后找到元素和下标映射不同的两个端点），然后中间的那部分就是要翻转的！
最后检查翻转部分的元素和下标是否对应！
*/
#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#define M 100005
using namespace std;
int n;
int a[M], b[M];
map<int, int>mp;
int main(){
int i;
while(cin>>n){
for(i=0; i<n; ++i){
cin>>a[i];
b[i]=a[i];
}
sort(a, a+n);
for(i=0; i<n; ++i)
mp[b[i]]=i;
for(i=0; i<n; ++i)
a[i]=mp[a[i]];
int L=-1, R=-1;
for(i=0; i<n; ++i)
if(a[i]!=i){
L=i;
break;
}
for(i=n-1; i>=0; --i)
if(a[i]!=i){
R=i;
break;
}
int ok=1;
if(L==-1 || R==-1)
cout<<"yes"<<endl<<"1 1"<<endl;
else{
reverse(a+L, a+R+1);
for(i=L; i<=R; ++i){
if(a[i]!=i){
ok=0;
cout<<"no"<<endl;
break;
}
}
if(ok)
cout<<"yes"<<endl<<L+1<<" "<<R+1<<endl;
}
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3885952.html，如需转载请自行联系原作者
