P1106-删数问题 - 从萌新到萌新的成长历程

题目传送门

题目思路

因为数字的性质，最大位小那么整个数一定小，所以要追求最小的数，就是贪心的追求从左到右的数小。

最开始的错误思路：对序列，其搜索最小的数的范围应该是第1个到第k+1个，因为要保证选这个数字之后这个数字右边还有足够数量的数字来组成这个数，也就是这个数右边的数字数量要大于等于n-k-1。所以下标为[0,k]，取找到的最左边的数字，然后缩小范围继续迭代。

#include <iostream>
#include <string>

using namespace std;

void searchmin(int l, int r, string s, int k)
{
    if (k == 0)
        return;
    char x = s[l];
    int str = 0;
    for (int i = l; i <= r; i++)
        if (s[i] < x)
        {
            x = s[i];
            str = i;
        }
    cout << x;
    searchmin(str + 1, r + 1, s, k - 1);
}
int main()
{
    string s;
    int k;
    cin >> s >> k;
    searchmin(0, k, s, s.length() - k);
}

但是没过，问题为：

第一个是我垃圾的代码习惯导致的初始化，str应该初始化为l，而不是0，因为如果for没有任何一个if成立，说明l的就是最小的，str应该为l，但是保持了初始化的0，导致寄。

第二个问题，前导0的问题，这里会输出前导的0，比如40输出为040,，寄。

第2.5个问题，输出那里简单的改成了不为0输出，又寄了，因为假设10 1结果应为0，但是没输出，淦。

补：上面的简单的修改不仅会导致上面的这个问题，还会导致中间0不输出，比如408输出为48.

修改，第一个改好，第二个简单判别修改即可AC

AC代码

#include <iostream>
#include <string>

using namespace std;

int p = 0;
void searchmin(int l, int r, string s, int k)
{
    if (k == 0 && p == 0)
        cout << "0";
    if (k == 0)
        return;
    char x = s[l];
    int str = l;
    for (int i = l; i <= r; i++)
        if (s[i] < x)
        {
            x = s[i];
            str = i;
        }
    if (x != '0' || p == 1)
    {
        p = 1;
        cout << x;
    }
    searchmin(str + 1, r + 1, s, k - 1);
}
int main()
{
    string s;
    int k;
    cin >> s >> k;
    searchmin(0, k, s, s.length() - k);
}