题目链接：https://codeforces.com/contest/1372/problem/C

题意

给出一个大小为 $n$ 的排列，每次操作可以选取一个连续子数组任意排列其中的元素，要求每个元素的位置必须与操作前不同，问将排列排为升序至少需要操作多少次。

题解

最多需要操作 $2$ 次，之后判断能否操作更少次即可。

如果已为升序，则不需要操作。

如果只有一个连续区间不为升序，如 $1,3,2,4,5$，只需要操作 $1$ 次。

否则需要操作 $2$ 次。

证明

第一次：选取整个数组，将所有 $a_i = i$ 的视为一体，在这个整体中每个元素循环右移一位，将余下 $a_i \neq i$ 的元素各自归位后也视为一体，在这个整体中的每个元素也循环右移一位。

第二次：选取整个数组，将第一次的两个整体中的元素各自循环左移一位。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n; cin >> n;

    int a[n + 1] = {};

    for (int i = 1; i <= n; i++)

        cin >> a[i];

    vector<int> v;

    for (int i = 1; i <= n; i++)

        if (a[i] != i)

            v.push_back(i);

    bool one_seg = true;

    for (int i = 1; i < v.size(); i++)

        if (v[i] - v[i - 1] > 1)

            one_seg = false;

    if (is_sorted(a + 1, a + 1 + n))

        cout << 0 << "\n";

    else if (one_seg)

        cout << 1 << "\n";

    else

        cout << 2 << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

巴特西

Codeforces Round #655 (Div. 2) C. Omkar and Baseball

题意

题解

证明

代码

最新文章

热门文章