Increasing and Decreasing （HDU-6852）(2020多校第七场)

Problem Description
Notice：Don’t output extra spaces at the end of one line.

Given n,x,y, please construct a permutation of length n, satisfying that:

• The length of LIS(Longest Increasing Subsequence) is equal to x.
• The length of LDS(Longest Decreasing Subsequence) is equal to y.

If there are multiple possible permutations satisfying all the conditions, print the lexicographically minimum one.

Input
The first line contains an integer $T$($1≤T≤100$), indicating the number of test cases.

Each test case contains one line, which contains three integers $n,x,y$($1≤n≤105,1≤x,y≤n$).

Output
For each test case, the first line contains ‘’YES’’ or ‘’NO’’, indicating if the answer exists. If the answer exists, output another line which contains n integers, indicating the permutation.

Sample Input
4
10 1 10
10 10 1
10 5 5
10 8 8

Sample Output
YES
10 9 8 7 6 5 4 3 2 1
YES
1 2 3 4 5 6 7 8 9 10
YES
1 2 3 5 4 10 9 8 7 6
NO

题意：让构造一个长度为n的序列，使得其最长递增子序列长度为x，最长递减子序列的长度为y。若无法构成自己输出 “NO”。

思路：

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
using namespace std;
vector<int> v;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, x, y;
    cin >> t;
    while (t--)
    {
        cin >> n >> x >> y;
        int a = sqrt(n);
        int b = n / a;
        if (a * b != n)
            b++;
        if (x + y > n + 1 || x + y < a + b)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;
            v.clear();
            for (int i = x; i; i--)
            {
                int xx = min(n - i + 1, y);
                for (int j = n - xx + 1; j <= n; j++)
                    v.push_back(j);
                n -= xx;
            }
            for (int i = v.size() - 1; ~i; i--)
                cout << v[i] << " \n"[!i];
        }
    }
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦