贪心|Balanced Ternary String【Codeforces Round #531 (Div. 3)D】【贪心、构造】贪心|构造

题目链接一道简单的构造，我们可以分成几个状态，因为所有的状态只有8个，所以，直接写每个状态即可，哎…… 被hack了…… 烦啊…… 谁让我写的好烂…… 好菜啊…… 呜呜呜

#include #include #include #include #include #include #include #include #include #include #include #include #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxN = 3e5 + 7; int N, num0, num1, num2, splay, head0, head1, head2, sum0, sum1, sum2; char a[maxN]; int N_0[maxN], N_1[maxN], N_2[maxN]; int main() { scanf("%d", &N); head0 = head1 = head2 = 1; num0 = num1 = num2 = 0; scanf("%s", a + 1); for(int i=1; i<=N; i++) { if(a[i] == '0') N_0[++num0] = i; else if(a[i] == '1') N_1[++num1] = i; else N_2[++num2] = i; } sum0 = num0; sum1 = num1; sum2 = num2; splay = N/3; //平衡点的中间值 if(sum0 == splay && sum1 == splay && sum2 == splay) { printf("%s\n", a+1); return 0; } if(sum0 > splay && sum1 <= splay && sum2 <= splay)//001 { for(int i=splay+1; i<=sum0; i++) { if(sum1 < splay) { a[N_0[i]] = '1'; sum1++; } else { a[N_0[i]] = '2'; sum2++; } } printf("%s\n", a+1); return 0; } if(sum0 <= splay && sum1 > splay && sum2 <= splay)//010 { int det = sum1 - splay; while(det--) { if(sum0 < splay) { a[N_1[head1++]] = '0'; sum0++; } else { a[N_1[num1--]] = '2'; sum2++; } } printf("%s\n", a+1); return 0; } if(sum0 > splay && sum1 > splay && sum2 <= splay)//011 { for(int i=splay+1; i<=sum0; i++) { a[N_0[i]] = '2'; } for(int i=splay+1; i<=sum1; i++) { a[N_1[i]] = '2'; } printf("%s\n", a+1); return 0; } if(sum0 <= splay && sum1 <= splay && sum2 > splay)//100 { int det = sum2 - splay; while(det--) { if(sum0 < splay) { a[N_2[head2++]] = '0'; sum0++; } else { a[N_2[head2++]] = '1'; sum1++; } } printf("%s\n", a+1); return 0; } if(sum0 > splay && sum1 <= splay && sum2 > splay)//101 { for(int i=splay+1; i<=sum0; i++) { a[N_0[i]] = '1'; } int det = sum2 - splay; while(det--) { a[N_2[head2++]] = '1'; sum1++; } printf("%s\n", a+1); return 0; } if(sum0 <= splay && sum1 > splay && sum2 > splay)//110 { int det = sum1 - splay; while(det--) { a[N_1[head1++]] = '0'; sum0++; } det = sum2 - splay; while(det--) { a[N_2[head2++]] = '0'; sum0++; } printf("%s\n", a+1); return 0; } return 0; }

【贪心|Balanced Ternary String【Codeforces Round #531 (Div. 3)D】【贪心、构造】】