题解：CF1765N Number Reduction

Patrickpanpan · 2024-08-06 20:00:43 · 题解

1.暴力：枚举每个位置的数，逐个比较。

2.错误贪心策略：每次删去数串最大的一个数字。

3.贪心策略：

部分最优解：每次枚举每一位数，每次得到的都是最小值。

全局最优解：每次找到最小值，则最终答案也为最小值。

证明（数学归纳法）：

1.当 k=1 ，做法与暴力相同，正确；

2.当 k>1 ，假设 k=m 正确，对于 k=m+1 ，再删掉 s 中的一个字符后最小的一个（贪心策略），正确。

code

#include<bits/stdc++.h>
using namespace std;
string s,smin,stemp;
int n;
int main()
{
    int T;
    cin>>T;
    for(int apple=1;apple<=T;apple++)
    {
        cin>>s>>n;
        for(int i=1;i<=n;i++)
        {
            smin=s;
            stemp=s;
            for(int j=0;j<s.size();j++)
            {
                stemp=s;
                stemp.erase(j,1);
                smin=min(smin,stemp);
            }
            s=smin;
        }
        while(s[0]=='0' && s.size()>1)s.erase(0,1);
        cout<<s<<endl;
    }
    return 0;
}
/*
举个栗子：
s=781864,k=3
第一遍循环：k=1,stemp=81864,71864,78864,78164,78184,78186
选出smin=71964,用smin替换s,s=71964

第二遍循环：k=2,stemp=1964,7164,7164,7194,7196
选出smin=1964,用smin替换s,s=1964

第三遍循环：k=2,stemp=964,164,194,196
选出smin=164,答案即为164
*/