SQ005. 强密码检验器 题解

#### 核心思路：找规律+分类讨论+贪心 “代码量很少的一道题” 观察到，（1）当长度小于6：需要插入字符补全长度，同时解决类型缺失和连续重复问题 （2）当长度在6与20之间：需要解决类型缺失和连续重复问题 （3）当长度大于20：则必须先删除多余字符到20，然后转化为类型2的问题 因为题目要求输出最少的修改步数，于是可以轻易想到贪心算法

我们有三个关键值需要计算（需要插入的字符数；缺失的类型数；需要替换的重复组数）

1.对于已是强密码---答案为0 2.对于长度<6，答案取三个值的最大值 3.对于长度6~20，答案取后两个值的最大值 4.对于长度>20，答案为（“删除次数+剩余需求最大值”）

而这道题难点主要在于长度大于20的类型。 我们可以发现：对于连续的子串，我们替换一个字母的效率高于删除的效率，所以我们在不得不删除的情况下我们应该优先处理那些等效率的子串（删除一个和替换一个对于将子串转化为非连续的是等价的），因此利用sort排序，然后贪心地删除处理len%3==0的子串的效率是最高的，这样的结果res也是最小的

详细代码如下

#include <bits/stdc++.h>
using namespace std;

const int N=10000;

int T;
string s;

int liannum(string s)
{
    int res=0;
    int n=s.size();
    int i=0;
    while(i<n)
    {
        int j=i;
        while(j<n&&s[j]==s[i])
            j++;
        res+=(j-i)/3;
        i=j;
    }
    return res;
}
int typenum(string s)
{
    bool n1=false,n2=false,n3=false;
    int x=3;
    for(char c:s)
    {
        if(c>='0'&&c<='9'&&!n1)
        {
            n1=true;
            x--;
        }
        else if(c>='a'&&c<='z'&&!n2)
        {
            n2=true;
            x--;
        }
        else if(c>='A'&&c<='Z'&&!n3)
        {
            n3=true;
            x--;
        }
    }
    return x;
}
bool isq(string s)
{
    int num=s.size();
    if(num<6||num>20)return false;
    bool n1=false,n2=false,n3=false;
    for(char c:s)
    {
        if(c>='0'&&c<='9')
            n1=true;
        if(c>='a'&&c<='z')
            n2=true;
        if(c>='A'&&c<='Z')
            n3=true;
    }
    if(!n1||!n2||!n3)return false;
    for(int i=2;i<num;i++)
        if(s[i]==s[i-1]&&s[i]==s[i-2])
            return false;
    return true;
}

bool cmp(int a,int b)
{
    return a%3<b%3;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s;
    if(isq(s))
    {
        cout<<0<<endl;
        return 0;
    }
    int num=s.size();
    int type=typenum(s);
    int lian=liannum(s);
    
    //收集连续重复长度>=3的片段
    vector<int>repeats;
    int i=0;
    while(i<num)
    {
        int j=i;
        while(j<num&&s[i]==s[j])
            j++;
        if(j-i>=3)
            repeats.push_back(j-i);
        i=j;
    }
    
    int res=0;
    if(num<6)
        res=max({6-num,type,lian});
    else if(num>=6&&num<=20)
        res=max(type,lian);
    else
    {
        //优先处理高效替换段落
        int del=num-20;//必须删除的数量
        sort(repeats.begin(),repeats.end(),cmp);//优先处理%后为0的
        int temp=del;
        //高效删除（每删除一个减少一次替换）
        for(int &len:repeats)//注意需引用修改
        {
            if(temp<=0)break;//必要删除（低效操作）结束,退出循环
            int needdel=min((len%3)+1,temp);
            len-=needdel;//删去后的长度
            temp-=needdel;//需求降低
        }
        //低效果删除（删除剩余字符）
        for(int &len:repeats)
        {
            if(temp<=0)break;
            int needdel=min(len,temp);
            len-=needdel;
            temp-=needdel;
        }
        //计算剩余替换需求
        int needreplace=0;
        for(int len:repeats)
        {
            needreplace+=len/3;
        }
        res=del+max(needreplace,type);
    }
    cout<<res<<endl;
    return 0;
}