題目鏈接：點擊查看

題目大意：給出a個0，b個1，c個2，d個3，要求構造一種序列，使得數列兩兩之間絕對值之差等于1，若不能構造輸出NO

題目分析：首先我們需要稍微討論一下特殊情況，那就是對于兩端的數字0和數字3，因為若這兩個數字，0只能和1匹配，也就是兩側必須都是1，同理，3的兩側必須都是2，所以我們可以簡單討論一下，分為兩種特殊情況：

a>b，此時的形式只能為01交叉，且首尾都為0，必須滿足：a-b==1&&c==0&&d==0，否則無解

d>c，同上，必須滿足：d-c==1&&a==0&&b==0，否則無解

處理完以上兩種特殊情況后，我們就來處理一般情況，首先我們先將四個數從中間切斷，分為兩組形式，因為上面的特殊情況已經處理完畢了，所以現在一定滿足a<=b&&c>=d，這樣我們就先讓每個0與1匹配，形成全為0 1排列的串，我們記為ans1，消耗完所有的a后，剩余的b我們記為bb，同理處理c和d，我們將此子串記為ans2，用2 3串消耗完d后，剩余的c我們記為cc，此時必須讓多余的bb和cc互相匹配，并且使其成為ans1與ans2的橋梁，所以必須用2 1串來匹配，這個時候必須滿足abs(cc-bb)<=1，允許相差至多為1，因為多出來的1可以放到最前面與0匹配，同理多出來的2可以放到最后面與3匹配，但若相差大于1的話就無法完全匹配了

到此為止，我們就已經討論完所有的情況了，按照上面的貪心策略構造答案就好了，記得準確輸出空格，以及及時return

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);if(a>b){if(a-b==1&&!c&&!d){printf("YES\n");while(b--)printf("0 1 ");printf("0\n");return 0;}elsereturn 0*printf("NO\n");}if(d>c){if(d-c==1&&!a&&!b){printf("YES\n");while(c--)printf("3 2 ");printf("3\n");return 0;}elsereturn 0*printf("NO\n");}b-=a;c-=d;if(abs(b-c)<=1){printf("YES\n");if(b>c)printf("1 ");while(a--)printf("0 1 ");for(int i=0;i<min(b,c);i++)printf("2 1 ");while(d--)printf("2 3 ");if(c>b)printf("2");}elsereturn 0*printf("NO\n");return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1265D Beautiful Sequence(贪心+构造+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。