codeforce每日一题链接
题目链接
题目分数:1500
题目描述
输入 $n(3≤n≤3e5 且 n\%3=0)$ 和长为 $n$ 的字符串$ s$,只包含$ 012$。
你需要修改 $s$ 中的字符,使得 $012$ 的数量都等于 $n/3$。
修改次数应当尽量少。
输出修改后的字典序最小的字符串。
样例
输入样例1
3
121
输出样例1
021
输入样例2
6
000000
输出样例2
001122
输入样例3
6
211200
输出样例3
211200
输入样例4
6
120110
输出样例4
120120
算法
(暴力枚举) $O(n)$
先填2,从后向前枚举,如果当前是1且1有多余的,就替换,否则替换0。再填0,从前向后枚举,如果当前是2并且2多余,就替换,否则替换1。再填1,如果0多余就从后向前填,如果2多余就从前向后填。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
string str;
cin>>str;
int a = n/3, b = n/3, c = n/3;
for(auto u : str)
if(u=='0') a--;
else if(u=='1') b--;
else c--;
per(i, 0, n-1)
if(c>0)
if(str[i]=='1' && b < 0) c--, b++, str[i] = '2';
else if(str[i]=='0' && a < 0) c--, a++, str[i] = '2';
rep(i, 0, n-1)
if(a>0)
if(str[i]=='2' && c < 0) a--, c++, str[i] = '0';
else if(str[i]=='1' && b < 0) a--, b++, str[i] = '0';
rep(i, 0, n-1)
if(str[i]=='2' && c < 0) b--, c++, str[i] = '1';
per(i, 0, n-1)
if(str[i]=='0' && a < 0) b--, a++, str[i] = '1';
cout<<str<<endl;
return 0;
}