2024牛客寒假算法基础集训营6 G 人生的起落题解

Martian148 / 2024-02-25 / 原文

Question

2024牛客寒假算法基础集训营6 G 人生的起落

定义一个三元组 $(x,y,z)$ 是 “v - 三元组” 当且仅当该三元组满足以下条件：

$x = z$
$x > y$

现在需要你构造一个 $n$ 个正整数组成的数组，所有元素之和恰好等于 $S$，且恰好有 $k$ 个长度威 $3$ 的连续子数组是 "v - 三元组"

Solution

贪心的想，如果用最少的元素和先构造出 $k$ 个 "v - 三元组"，剩下的元素随意放在后面就好了

那么简单得，最少的方案就是 2 1 2 1 2 1 ......

如果后面没有位置了，即 $n = 2k + 1$

那么就先集体增加 $2$，然后增加 $1$ 的位置

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve() {
    LL n, S, k; cin >> n >> S >> k;
    vector<LL> a(n + 1);
    int m = 2 * k + 1;
    if (k == 0) {
        S -= n;
        if (S < 0) {
            cout << -1 << endl;
            return;
        }
        for (int i = 1; i <= n; i++) 
            a[i] = 1;
        a[1] += S;
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
        return;
    }
    if (n < m) {
        cout << -1 << endl;
        return;
    }
    else if (n == m) {
        LL sum_1 = k * 1, sum_2 = (k + 1) * 2;
        S -= sum_1 + sum_2;
        if (S < 0) {
            cout << -1 << endl;
            return;
        }
        LL x = S / (k + 1); S -= x * (k + 1);
        for (int i = 1; i <= m; i += 2) {
            a[i] = 2 + x;
        }
        for (int i = 2; i <= m; i += 2) {
            if (S > 0) {
                if (x == 0) {
                    cout << -1 << endl;
                    return;
                }
                a[i] = 2; S -= 1;
            }
            else a[i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    else if (n > m) {
        LL sum_1 = k * 1, sum_2 = (k + 1) * 2;
        S -= sum_1 + sum_2;
        for (int i = 1; i <= m; i++) {
            if (i & 1) a[i] = 2;
            else a[i] = 1;
        }
        for (int i = m + 1; i <= n; i++) {
            a[i] = 1; S -= 1;
        }
        if (S < 0) {
            cout << -1 << endl;
            return;
        }
        a[m + 1] += S;
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}