【CodeForces】1608B Build the Permutation题解

题目大意

给定 $n, a, b$，求是否能构造出 $n$ 个数（$1 \sim n$）的排列，满足：

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

部分极大值：$\exists\ 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, \ldots, max\ +$ 有序序列
• $a + 1 = b$：$min, max, min, max, \ldots, min\ +$ 有序数组
• $a = b$（从 $min$ 开始）：$min, max, min, max, \ldots\ +$ 有序数组
• $a = b$（从 $max$ 开始）：$max, min, max, min, \ldots\ +$ 有序序列

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

所以我们判断一下 $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;
}