Codeforces 1608B. Codeforces Round #758 (Div.1 + Div. 2)(思维)
原题链接
简单
作者:
小小_88
,
2022-12-01 00:41:24
,
所有人可见
,
阅读 189
Build the Permutation
C++ 代码
/*
本题要求我们给 1 ~ n 排列,使得序列中有 a 个极大值、b 个极小值
首先知道一个序列中的极大值和极小值数量之差不可能 >= 2,因此如果 abs(a - b) >= 2,直接判断无解
剩下只有三种情况:
1. a < b
2. a > b
3. a = b
对于情况 1,只有这种情况:\/\/ ... \/\/
对于情况 2,只有这种情况:/\/\ ... /\/\
对于情况 3,有两种情况:/\/\ ... /\/ 或 \/\/ ... \/\
接下来我们只需要分别构造出这些情况即可,这里给出一个构造的规律,对于 1 ~ 5,我们可以构造出极大值
和极小值最多的情况:
3 4 5 1 2
1 2 3 4 5
因此对于以上三种情况,我们都可以用 a + b 个数构造出连续的 a 个极大值和 b 个极小值。
剩下的 n - a - b 个数在边上作为边界。
对于情况 1,我们可以取 n 作为左边界,取 a + b + 1 ~ n - 1 作为右边界,取 1 ~ a + b 构造极大值极小值
对于情况 2,我们可以取 2 ~ n - a - b 作为左边界,取 1 作为右边界,取 n - a - b + 1 ~ n 构造极大值极小值
对于情况 3,我们可以取 1 ~ n - a - b - 1 作为左边界,取 n 作为右边界,取 n - a - b ~ n - 1 构造极大值极小值
*/
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 100010;
int n, a, b;
int p[N];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &a, &b);
if(abs(a - b) >= 2 || a + b + 2 > n)
{
puts("-1");
continue;
}
if(a < b)
{
p[1] = n;
for(int i = a + b + 2; i <= n; i++) p[i] = i - 1;
int j = 1;
for(int i = 2; i <= a + b + 1; i += 2) p[i] = j++;
for(int i = 3; i <= a + b + 1; i += 2) p[i] = j++;
}
else if(a > b)
{
p[n] = 1;
for(int i = 1; i <= n - a - b - 1; i++) p[i] = i + 1;
int j = n - a - b + 1;
for(int i = n - a - b + 1; i <= n - 1; i += 2) p[i] = j++;
for(int i = n - a - b; i <= n - 1; i += 2) p[i] = j++;
}
else
{
p[1] = 1;
for(int i = a + b + 2; i <= n; i++) p[i] = i;
int j = 2;
for(int i = 3; i <= a + b + 1; i += 2) p[i] = j++;
for(int i = 2; i <= a + b + 1; i += 2) p[i] = j++;
}
for(int i = 1; i <= n; i++) printf("%d ", p[i]);
puts("");
}
return 0;
}