Codeforces Round #258 (Div. 2) B. Sort the Array-蒲公英云

Codeforces Round #258 (Div. 2) B. Sort the Array

冷不防 2024-03-29 14:53 156阅读 0赞

Problem - B - Codeforces

题意：

给定一个数列，问你能否把其一段子段反转之后使其单调递增

思路：

结论很简单，当且仅当数列中只有一段单调递减的子段且反转之后能单调递增

重点在于我们怎么去写它

像这种关注数列单调性的有种很方便的写法

创建一个和a一样的数组，然后排序，把这两个数列对比一下就行

详细看代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=1e5+10;
int n,ok=1;
int a[mxn],b[mxn];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    ok=1;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]) ok=0;
    }
    if(ok){
        cout<<"yes"<<'\n';
        cout<<"1 1"<<'\n';
        return 0;
    }
    int l,r;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]){
            l=i;
            break;
        }
    }
    for(int i=n;i>=1;i--){
        if(a[i]!=b[i]){
            r=i;
            break;
        }
    }
    reverse(a+l,a+1+r);
    ok=1;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]) ok=0;
    }
    if(ok){
        cout<<"yes"<<'\n';
        cout<<l<<" "<<r<<'\n';
    }else cout<<"no"<<'\n';
}