Codeforces Round #531 (Div. 3) D. Balanced Ternary String （思维）

59 阅读 0 评论 39 点赞

我是靠谱客的博主犹豫巨人，最近开发中收集的这篇文章主要介绍Codeforces Round #531 (Div. 3) D. Balanced Ternary String （思维），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题目意思：
给你只包含0,1,2的字符串，保证长度为3的倍数，让你替换某些字符，得到的新字符串包含的0,1,2的个数相等，要求替换次数最少，并且在此前提下字典序最小

思路：
把数量不够的的字符按照字典序放在一个数组sum中（例如：需要增加2个‘0’和3个‘1’，那么这个数组为[0, 0, 1, 1, 1]），把要替换的数标记一下，然后从头开始跑，如果st[i]能被替换，并且sum[pos] < st[i]，也就是这个替换可以使字典序变小，那么就直接替换。否则的话还剩下两种情况，一个就是跳过st[i]，不替换它，另一种就是剩下的可以被替换的字符和必须要被替换的字符的数量相等了，那么之后的必须一个挨一个的替换。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 3 * 1e5 + 100;

char st[maxn];
int sum[maxn];          //用来存放需要替换的字符

int main()
{
    //freopen("in.txt", "r", stdin);
    int n;
    int num[5] = {0};
    cin >> n;
    scanf("%s", st);
    for(int i = 0; i < n; ++ i) {       //统计每种字符的个数
        if(st[i] == '0')    num[0] ++; 
        else if(st[i] == '1')   num[1] ++;
        else if(st[i] == '2')   num[2] ++;
    }
    int b[5];             //用来存放每种字符是需要减少还是需要增加
    int top = 0;         //sum数组的边界
    int pos = 0;         //代表当前跑到sum数组的某个位置
    for(int i = 0; i <= 2; ++ i) {      //统计每种字符的减少量，b[i]为正则说明需要减少，为负则需要增加
        b[i] = num[i] - (n / 3);
    }
    for(int i = 0; i <= 2; ++ i) {        //把需要替换的字符全部弄到sum数组中去
        if(b[i] < 0) {
            while(b[i] < 0) {
                sum[top++] = i;
                b[i] ++;
            }
        }
    }
    for(int i = 0; i <= 2; ++ i) {     //现在num数组负责记录能被替换的字符的数量
        if(b[i] <= 0)       //如果其本身的数量就少，就没有一个这种字符可以被替换
            num[i] = 0;
    }
    for(int i = 0; i < n; ++ i) {
        int cnt = st[i] - '0';
        //当前的这个字符得能被替换，也就是b[cnt] > 0，sum数组不能越了边界，也就是pos < top, 当前剩下的这个种类的字符能被替换的数量一定不能小于必须要被替换的数量，也就是num[cnt] > b[cnt]
        if(b[cnt] > 0 && pos < top && num[cnt] >= b[cnt]) { 
        //如果将st[i]替换成sum[pos]使得字典序增大就直接替换，对应sum[pos] < cnt
        //不然的话如果sum数组中剩下的数目等于能被替换的字符数量了，那么接下来就得一一替换了，对应于top - pos == num[0] + num[1] + num[2]
        //或者说当前种类的字符必须被替换掉的字符等于剩下的字符数量了，那么接下来遇到这种字符就需要一一替换成sum[pos]，跟上面一个差不多的道理，对应于b[cnt] == num[cnt]
            if(sum[pos] < cnt || top - pos == (num[0] + num[1] + num[2]) || (b[cnt] == num[cnt] && b[cnt] > 0)) {
                st[i] = sum[pos++] + '0';
                b[cnt] --;
                if(b[cnt] == 0)    //弄完之后记得判断一下这种字符是否还能再被替换，如果不能及时把num[cnt]清空为0，不然在后面还会继续替换这种字符，使得这种字符数量小于n/3
                    num[cnt] = 0;
            }
            if(num[cnt] > 0)
                num[cnt] --;
        }
    }
    cout << st << endl;
    return 0;
}