Beautiful Sequence

Created by LXC on Fri Aug 4 20:55:15 2023

https://codeforces.com/problemset/problem/1264/B

ranting: 1900

tag: brute force, constructive algorithms, greedy

problem

给出a,b,c,d四个正整数。满足$0 < a+b+c+d \le 10^5$

分别代表你有a个0，b个1，c个2，d个3。

你需要将这些数组成一个序列，满足任意相邻直接的差的绝对值不超过1。

输出构造方案。

solution

如果先摆好所有0和2，这时候再摆1，则可以放在任意两个数的间隙或序列两侧。

最后放3，则放置的位置两侧只能是2

构造的规则可以是首先0和1交替摆放，直到0没有了，然后交替摆放1和2，最后1没有了，交替摆放2和3.

确定开始摆放的数字，总共4种。只要有一种能成功构造就行。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

vector<int> ans;
int a[4];
int sum = 0;

void sol() {
    for (int i = 0; i < 4; i++)
        cin >> a[i], sum += a[i];
    for (int i = 0; i < 4; i++) {
        if (a[i] == 0)
            continue;
        ans.push_back(i);
        a[i]--;
        int c = i;
        for (int j = 1; j < sum; j++) {
            if (c - 1 >= 0 && a[c - 1]) {
                ans.push_back(--c);
                a[c]--;
            } else if (c + 1 < 4 && a[c + 1]) {
                ans.push_back(++c);
                a[c]--;
            } else
                break;
        }
        if (ans.size() == sum) {
            cout << "YES\n";
            for (int i : ans) {
                cout << i << " ";
            }
            cout << "\n";
            return;
        }
        while (ans.size())
            a[ans.back()]++, ans.pop_back();
    }
    cout << "NO\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}