题目描述

链接：https://ac.nowcoder.com/acm/contest/9982/F
来源：牛客网

牛牛有一个数组，数组元素是1到n的排列，即数组的值在1~n范围内，且每个数字仅出现1次。
牛牛想要将该数组变为升序排列的，他可以进行如下的操作。

首先他要确定一个长度k，k的范围在1~n之间。
接下来他将会进行若干次操作。在每***作中他都可以选择一段长度为k的子数组，然后进行区间的翻转操作。

他可以做任意次数的操作，但是要求他每次选择的子数组区间满足Li <= Li+1，并且区间长度等于一开始选定的k，也就是说一旦某一次操作选择了数组的某个位置进行区间翻转操作，下一次做区间翻转的位置将会比上一次更靠右。

牛牛发现，并不总是存在一个k可以使得数组排序变为有序，请你告诉牛牛是否存在一个k能够在满足规则的情况下完成排序。

输入描述

第一行输入一个正整数n(1 <= n <= 1e5)表示数组的大小。
接下来输出一行n个正整数表示一个排列，即每个数的大小范围在1到n且每个正整数仅出现一次。

输出描述

如果存在至少一个k能够使牛牛完成排序，请先在一行中输出一个"yes"，然后另起一行输出一个可以满足排序的k，要求k的范围在[1,n]之间，如果有多解，你可以输出任意一个。反之如果不存在任何一个k可以完成排序，请直接在一行输出一个"no"

解题思路

抓住题目的重点下一个做区间翻转的位置将会比上一次更靠右，且翻转区间长度为k是不变的，顺着这个思路，当数组 f 的下标为 i 的元素的值不等于 i ，我们需要在数组中找到一个元素的值等于 i ，这两个元素的之间的距离就是翻转区间k。所以我们只需要在确定 k 之后遍历一遍数组，当下标与元素的值不相等时翻转，若翻转后还是不相等，则直接判定为不能完成排序（因为遍历到当前元素后面的元素时已经无法改变前面元素的顺序）。

解题技巧

频繁进行数组翻转操作效率较低，可以使用双端队列，通过不同端的入队及出队来模拟翻转。

c++代码

#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5;

int f[maxn], n, k;
int ff[maxn];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &f[i]);
        if(f[i] == 1 && i != 1) k = i;
    }
    int flag = 0, pos;
    //寻找表示区间长 k ,以及第一个下标与值不相等的元素 pos 
    if(!k) {
        for(int i = 1; i <=n; i++) {
            if(!flag && i != f[i]) {
                pos = i; flag = 1;    
            }
            else if(flag &&f[i] == pos){
                k = i - pos + 1; break;
            }
        }
    }
    if(!k) { printf("yes\n1"); return 0; }

    deque<int> q;//双端队列 
    for(int i = pos; i < pos+k-1; i++) {
        q.push_back(f[i]);
    }
    flag = 0;
    int t = 0;
    int temp = pos;
    for(int i = pos+k-1; i <= n; i++) {
        if(!t) q.push_back(f[i]); //t=0表示从尾巴入队以及出队 
        else q.push_front(f[i]);//t=1表示从头入队以及出队 
        if(q.back() == temp) {
            q.pop_back(); t = 1;
        }
        else if(q.front() == temp) {
            q.pop_front(); t = 0;
        }
        else {
            flag = 1; break;
        }
        temp++;
    }
    if(!flag) {//最后还需判断队列里面的元素是否排序正确 
        int j = 0;
        for(deque<int>::iterator it = q.begin(); it != q.end(); it++) {
            ff[j++] = *it;
        }
        if(ff[0] == temp) {
            for(int i = 0; i < j; i++) {
                if(ff[i] != temp+i) flag = 1;
            }
        }
        else {
            for(int i = 0; i < j; i++) {
                if(ff[i] != n-i) flag = 1;
            }
        }
    }
    if(flag) printf("no");
    else printf("yes\n%d", k);
    return 0;
}