[CF1793B] Fedya and Array 题解
qifan_maker
·
·
题解
题目链接
洛谷
Codeforces
题意分析
有一个长度为 n 的数组 a，排列成一个圆，相邻两个数的差为 1。
注意，元素 a_n 和 元素 a_1 是相邻元素。
我们把同时小于左右两个相邻元素的元素值称为局部最大值，把同时小于左右两个相邻元素的元素值称为局部最小值。
由于 相邻两个数的差为 1，所以局部最大值相邻的数一定都比它小 1，而局部最小值相邻的数一定都比它大 1。
现在，题目告诉我们 所有局部最大值的和 —— x 与 所有局部最小值的和 —— y，要我们求出 任何最小长度的匹配数组。
题目解法
这道题其实不需要很复杂的算法，
只要找到规律，就变得很简单了。
我们可以举个例子:
x = 5~~~y=-2
可以看到，这个例子中：
唯一的局部最大值就是正上方 4 5 4 中的 5，而所有局部最大值的和自然也就是 5 了。
唯一的局部最小值就是正下方 -1 -2 -1 中的 -2，而所有局部最小值的和自然也就是 -2 了。
满足条件，所以我们可以推导出：
也就是输出 x,x-1,x-2,...,y,y+1,y+2,...,x-1。
但是题目还问了一共有多少个数，通过上图可以发现，
至少需要 $2(x-y)$ 个数。
##### 可行性证明
$x \to y \to (x-1)$ 可以确保 $x$ 相邻的数都比它小 $1$，而 $y$ 相邻的数都比它大 $1$。
由于 $x \to y$ 和 $y \to (x-1)$ 都是有序地 $+1$ 或 $-1$ 的，所以可以确保只有唯一一个局部最大值和局部最小值，从而确保所有局部最大值和所有局部最小值为 $x$ 和 $y$。
时间复杂度为 $\mathcal{O}(∑n)$。
### [AC](https://www.luogu.com.cn/record/102111258) code
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
int x,y;
cin >> x >> y;
cout << 2*(x-y) << endl;
for (int i=x;i>=y;i--){
cout << i << " ";
}
for (int i=y+1;i<x;i++){
cout << i << " ";
}
cout << endl;
}
return 0;
}
```