CF1608B Build the Permutation

2021-12-13

字数统计: 512字 | 阅读时长≈ 2分

题目大意

给定$n, a, b$,求是否能构造出$n$个数($1$~$n$)的排列,满足:

有$a$个部分极大值
有$b$个区间极小值

部分极大值：$\exist i, j, k$,满足$1 \le i < j < k \le n,$ 并且$ a_i < a_j, a_j > a_ k$。

此时$a_j$被称为部分极大值。原题地址

思路

我们可以发现以下性质: * 两个部分极大值中间一定存在一个部分极小值

两个部分极小值中间一定存在一个部分极大值
$a_1,a_n$这两个数一定不是部分极大值/极小值。

然后我们就可以继续往下推: * $a + b \le n - 2$

也就是说极大值数量与极小值数量之和最多为$n-2$

$|a - b| \le 1$

因为根据前面得出的性质,合法情况一定是 "极大值,极小值,极大值..."(或者反过来),这么排列的

具体做法

那么根据上述结论,我们无非这么四种构造结果,

我用$max$表示部分极大值,$min$表示部分极小值:

$a = b + 1$ : $max,min,max,min,max + $ 有序序列
$a + 1 = b$ : $min,max,min,max,min + $ 有序数组
$a = b$ : $min,max,min,max + $ 有序数组
$a = b$ : $max,min,max,min + $ 有序序列

实际上第三种和第四种效果是一样的,所以也就是三种。

所以我们判断一下$a,b$的大小关系,然后按照上面表中的方法去构造即可。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
 
const int maxN = 1e5 + 7;
 
int T, n, a, b, ans[maxN];
 
 
int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &a, &b);
        if(a + b + 2 > n || abs(a - b) > 1) {
            printf("-1\n");
            continue;
        }
        int l = 1, r = n, flag = (a > b) ? 1 : 0;
        for(int i = 1; i <= n; ++i) {
            if(flag)
                ans[i] = l++;
            else    
                ans[i] = r--;
            if(i <= a + b)
                flag ^= 1;    
        }
        for(int i = 1; i <= n; ++i)
            printf("%d ", ans[i]);
        printf("\n");  
    }
    return 0;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/12/13/CF1608B/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！