[数据结构与算法]B. Build the Permutation

原题

题目大意

• 定义q[i - 1] < q[i] > q[i + 1]为局部最大值q[i - 1] > q[i] < q[i + 1]为局部最小值
• 问能否在所给的数据范围内找到一个满足局部最大值个数a和局部最小值个数b要求的序列

思路

• 将数从小到大排列，按最大最小依次拿出
• 实践发现这样可得最佳状态
• a和b满足a + b <= n - 2 abs(a + b) <= 1
• 不满足此条件的则无法找到相应序列

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;;

int n, m, t;
int arr[N];

int main()
{
    cin >> t;

    while(t --)
    {
        memset(arr, 0, sizeof arr);//记得初始化
        int a, b;
        cin >> n >> a >> b;

        if(a + b + 2 > n || abs(a - b) > 1)
        {
            puts("-1");
            continue;
        }

        int l = 1, r = n;
        int falg;
        falg = (a > b) ? 1 : 0;//用来判断是否满足需要的个数

        for(int i = 1; i <= n; i ++)
        {
            if(falg) arr[i] = l ++;
            else arr[i] = r --;
            if(i <= a + b) falg ^= 1;//取相反布尔值
        }

        for(int i = 1;i <= n; i ++) cout << arr[i] << " " ;
        puts("");
    }

    return 0;
}