AT_arc132_b Shift and Reverse 题解

题意

有一个序列，你可以将它翻转或者将第一个数挪到最后面，求最小的操作使得序列升序的次数。数据保证有解。

思路

首先我们可以看到题目中说保证一定有解，因此我们可以发现挪动的方式一定是将前面的数整体挪到到后面或者翻转后将前面的数移到后面再翻转回来。看一个例子：

3 4 5 6 7 8 9 10 1 2

答案显然是将序列整体翻转后将 2 1 挪到最后面然后再翻转回来，次数为 4。

有了上面的结论，我们就可以分类讨论一下：

• 有序。 直接输出 \(0\)。
• 直接移动。 答案为 \(n - a_1 + 1\)。
• 翻转后移动再翻转。 答案为 \(a_1 +1\)。

对于后面的两种情况，取最小值即可。

代码

#include <iostream>

using namespace std;

int n, a[3];

signed main() {
    cin >> n >> a[1] >> a[2];
    if (a[1] == 1 && a[2] == 2) {
        cout << 0;
    } else {
        cout << min(a[1] + 1, n - a[1] + 1);
    }
}

喜欢这篇文章？分享给你的朋友吧（￣︶￣）↗