站外题求助

输入三个正整数分别表示 a、b 和 c 三个字符所能使用的数量。用这些字符构造一个最长的字符串，需要保证其中不包含连续三个相同的字符。

我把输入排序，然后分能全部用上和不能全部用上两种情况讨论。主要问题在于能全部用上的构造里面，如何证明我的这种构造一定是对的？或者是否存在反例？

我的构造大概是，先全部用数量最多的那个字符来填充，然后类似于按模 3 覆盖，用其它两种字符插入进来间隔它。这部分对应代码 else 的部分。

CPP

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        array<pair<int,char>,3> ap({{a,'a'},{b,'b'},{c,'c'}});
        sort(ap.begin(),ap.end(),greater<>());
        
        if(ap[0].first>=2*(ap[1].first+ap[2].first)+2){
            string ans;
            int t=ap[1].first+ap[2].first;
            ans+=ap[0].second;
            ans+=ap[0].second;
            for(int i=0;i<t;++i){
                if(ap[1].first!=0){
                    ans+=ap[1].second;
                    --ap[1].first;
                }
                else{
                    ans+=ap[2].second;
                    --ap[2].first;
                }
                ans+=ap[0].second;
                ans+=ap[0].second;
            }
            return ans;
        }
        else{
            string ans(a+b+c,ap[0].second);
            int i=2;
            while(i<ans.length()){
                if(ap[1].first>0){
                    ans[i]=ap[1].second;
                    --ap[1].first;
                }
                else if(ap[2].first>0){
                    ans[i]=ap[2].second;
                    --ap[2].first;
                }
                else{
                    return ans;
                }
                i+=3;
            }
            i=3;
            while(i<ans.length()){
                if(ap[1].first>0){
                    ans[i]=ap[1].second;
                    --ap[1].first;
                }
                else if(ap[2].first>0){
                    ans[i]=ap[2].second;
                    --ap[2].first;
                }
                else{
                    return ans;
                }
                i+=3;
            }
            i=1;
            while(i<ans.length()){
                if(ap[1].first>0){
                    ans[i]=ap[1].second;
                    --ap[1].first;
                }
                else if(ap[2].first>0){
                    ans[i]=ap[2].second;
                    --ap[2].first;
                }
                else{
                    return ans;
                }
                i+=3;
            }
            return ans;
        }
        
    }
};

讨论操作

回复

相关推荐

站外题求助