Minimize Permutation Subarrays
题面翻译
给定一个长度为 \(n\) 的排列 \([p_1, p_2, ..., p_n]\) ，任选两个元素（可以相同）并交换一次，使得其所有子段中排列（长度不一定为 \(n\) ）的个数最少，输出被交换的元素的位置（下标从 \(1\) 开始）。
对于样例 \(1\) ，如果交换 \(p_1\) 和 \(p_2\) ，则可以得到排列 $ [2, 1, 3] $ ，含有 \(3\) 个为排列的子段（ $ [1] $ , $ [2, 1] $ , $ [2, 1, 3] $ ）；
如果交换 \(p_1\) 和 \(p_3\) ，则可以得到排列 $ [3， 2， 1] $ ，含有 \(3\) 个为排列的子段（ $ [1] $ , $ [2， 1] $ , $ [3， 2， 1] $ ）；
如果交换 \(p_2\) 和 \(p_3\) ，则可以得到排列 $ [1, 3, 2] $ ，含有 \(2\) 个为排列的子段（ $ [1] $ ， $ [1, 3, 2] $ ）。
故当交换 \(p_2\) 和 \(p_3\) 时最优。
对于样例 \(3\) ，交换第 \(2\) 和第 \(5\) 个元素后，得到 \([1, 4, 2, 5, 3]\) ，仅包含两个为排列的子段（ \([1]\) ， \([1, 4,, 2, 5, 3]\) ）。可以证明这是最优的情况。
题目描述
You are given a permutation $ p $ of size $ n $ . You want to minimize the number of subarrays of $ p $ that are permutations. In order to do so, you must perform the following operation exactly once:
- Select integers $ i $ , $ j $ , where $ 1 \le i, j \le n $ , then
- Swap $ p_i $ and $ p_j $ .
For example, if $ p = [5, 1, 4, 2, 3] $ and we choose $ i = 2 $ , $ j = 3 $ , the resulting array will be $ [5, 4, 1, 2, 3] $ . If instead we choose $ i = j = 5 $ , the resulting array will be $ [5, 1, 4, 2, 3] $ .
Which choice of $ i $ and $ j $ will minimize the number of subarrays that are permutations?
A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).
An array $ a $ is a subarray of an array $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
输入格式
The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 2\cdot 10^5 $ ) — the size of the permutation.
The next line of each test case contains $ n $ integers $ p_1, p_2, \ldots p_n $ ( $ 1 \le p_i \le n $ , all $ p_i $ are distinct) — the elements of the permutation $ p $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .
输出格式
For each test case, output two integers $ i $ and $ j $ ( $ 1 \le i, j \le n $ ) — the indices to swap in $ p $ .
If there are multiple solutions, print any of them.
样例 #1
样例输入 #1
8
3
1 2 3
3
1 3 2
5
1 3 2 5 4
6
4 5 6 1 2 3
9
8 7 6 3 2 1 4 5 9
10
7 10 5 1 9 8 3 2 6 4
10
8 5 10 9 2 1 3 4 6 7
10
2 3 5 7 10 1 8 6 4 9
样例输出 #1
2 3
1 1
5 2
1 4
9 5
8 8
6 10
5 4
分析
要让子序列的个数最少. 题目要求一个合法的长度为 k 的子序列需要包含元素1到k, 且子序列需要是连续的一段
那么每个子序列肯定要从1开始吧, 然后下一个就要找2吧, 那如果1和2隔得很远, 比如1在开头, 2在结尾, 那么我们很明显就只有两个子序列, 一个是1, 另一个是1到n
所以第一反应是把1和2放到开头和结尾, 这样很明显子序列是最少的, 但是交换只能进行一次, 如果1和2都在中间, 我们没办法通过一次交换达到这个结果
我们再考虑别的方法, 例如子序列 1 6 2, 这肯定是不合法的吧, 因为我们在囊括1和2的时候包进去了一个比子序列长度大的数, 那我们不一定非要让1和2在开头和结尾, 我们只需要让最大的数在1和2中间即可
仔细解释一下, 因为任何长度大于二的子序列都需要2和1, 我们包含2和1的时候就肯定要包含最大的数n, 要让这个子序列合法, 我们就只能把整个序列包含进去才能合法, 这样子我们就只有两个子序列, 一个只有1, 一个有1到n, 就是最少的
具体方法是:
- 如果1和2中间没有数字, 看看把1和n交换还是2和n能达到上述条件
- 如果1和2中间有别的数字, 选出最小的那个和 n 交换
注意: 不一定1就在左边2就在右边, 不要惯性思维
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while(t--)
{
int n; cin >> n;
int pos1, pos2, posmax; //记录1, 2, n的位置
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(a[i] == 1) pos1 = i;
else if(a[i] == 2) pos2 = i;
else if(a[i] == n) posmax = i;
}
if((pos1 < posmax && posmax < pos2) || (pos2 < posmax && posmax < pos1))
//别把n换出去就行
{
cout << pos1 << ' ' << pos2 << endl;
continue;
}
else
{
if(abs(pos1 - pos2) == 1) //中间没有空位
{
if(posmax < min(pos1, pos2))
{
cout << min(pos1, pos2) << " " << posmax << endl;
}
else
{
cout << max(pos1, pos2) << " " << posmax << endl;
}
continue;
}
int minn = 1e9, minpos = pos1;
for(int i = min(pos1, pos2) + 1; i < max(pos1, pos2); i++)
{
if(a[i] < minn)
{
minn = a[i], minpos = i;
}
}
cout << minpos << ' ' << posmax << endl;
}
}
}