旺崽的博客

要么天赋异禀，要么天道酬勤

0%

2021牛客寒假算法基础集训营2 F.牛牛与交换排序

发表于 分类于 Valine：

题目链接

题目描述

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

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

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

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

输入描述:

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

输出描述:

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

反之如果不存在任何一个k可以完成排序，请直接在一行输出一个 “no”

示例1

输入

1
2
5
5 2 1 4 3

输出

1
2
yes
3

示例2

输入

1
2
5
1 2 3 4 5

输出

1
2
yes
1

示例3

输入

1
2
5
5 4 3 2 1

输出

1
2
yes
5

思维+模拟~
因为每次区间的选择都只能往右走，也就是对某一位置 $i$，若它的 $pos[i]$(它在所给数组中的位置)在右边，那么必须只能一次操作将其换回原位，也就是说我们只要找到第一个不在原位置的 $i$，那么 $k$ 一定就是 $pos[i]-i+1$~
找到该位置后我们就要去想用什么数据结构能模拟一次排序数组的过程，显然这个数据要能从头取，也能从尾取，所以很容易想到双端队列，对翻转这个操作我们通常的技巧就是设置一个翻转标记，而不需要真的把队列翻转，例如原本翻转标记 $flag=0$，我们这是从队头弹出，队尾插入，翻转后只需要从队尾弹出，队头插入即可，STL 里面就有 $deque$ 这个数据结构，不熟悉的同学可以去自学一下~
整个模拟过程简单描述如下：

  • 先存 $k$ 个元素
  • 每次拿位置 $i$ 和队头队尾进行匹配，匹配成功执行相应的弹出插入操作和修改对应的翻转标记，不匹配直接输出 $no$ 即可

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int n, k, flag = 0, a[N], pos[N];
deque<int> q;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (pos[i] != i) {
            k = pos[i] - i + 1;
            break;
        }
    }
    if (!k) {
        cout << "yes\n" << "1";
        return 0;
    }
    for (int i = 1; i <= k; i++) q.push_back(a[i]);
    for (int i = k + 1; i <= n + k; i++) {
        if (!(flag % 2)) {
            if (i - k == q.front()) q.pop_front();
            else if (i - k == q.back()) flag ^= 1, q.pop_back();
            else {
                cout << "no";
                return 0;
            }
        } else if (flag % 2) {
            if (i - k == q.back()) q.pop_back();
            else if (i - k == q.front()) flag ^= 1, q.pop_front();
            else {
                cout << "no";
                return 0;
            }
        }
        if (i <= n) {
            if (flag % 2) q.push_front(a[i]);
            else q.push_back(a[i]);
        }
    }
    cout << "yes\n" << k;
    return 0;
}