Codeforces 1265D - Beautiful Sequence 题解

比赛的时候太蠢了。

题解 #

这题的关键在于答案的第一个数要么是最小的数要么是第二小的数,两种情况都试一下。填某一位的时候,要么是上一位加一,要么是上一位减一,先试减 1,如果没有减 1 可以用了就试加 1,如果加一也没有了那就可以停止去尝试以另一个数开头的情况了。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int a[5]={0},cnt[4],sum=0;
    forn(i,4) cin>>cnt[i],a[i]=cnt[i],sum+=a[i];
    int start;
    forn(i,4){
        if(a[i]){
            start=i;
            break;
        }
    }
    vector<int> ans(sum);
    bool flag=0;
    for(int j=0;j<2&&!flag;j++){
        forn(i,4) a[i]=cnt[i];
        if(start+j>3||a[start+j]==0) break;
        ans[0]=start+j;
        a[start+j]--;
        for(int i=1;i<sum;i++){
            if(ans[i-1]==0){
                if(a[1]){
                    ans[i]=1;
                    a[1]--;
                }else break;
            }else if(ans[i-1]==3){
                if(a[2]){
                    ans[i]=2;
                    a[2]--;
                }else break;
            }else{
                if(a[ans[i-1]-1]){
                    ans[i]=ans[i-1]-1;
                    a[ans[i-1]-1]--;
                }else if(a[ans[i-1]+1]){
                    ans[i]=ans[i-1]+1;
                    a[ans[i-1]+1]--;
                }else break;
            }
            if(i==sum-1) flag=1;
        }
        if(sum==1) flag=1;
    }
    if(flag){
        cout<<"YES\n";
        for(int it:ans) cout<<it<<' ';
    }else cout<<"NO";
    return 0;
}