【Codeforces】1230B - Ania and Minimizing

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/101830422

Problem Description：

Ania has a large integer S. Its decimal representation has length n and doesn't contain any leading zeroes. Ania is allowed to change at most k digits of S. She wants to do it in such a way that S still won't contain any leading zeroes and it'll be minimal possible. What integer will Ania finish with?

Input Specification:

The first line contains two integers n and k (1≤n≤200000, 0≤k≤n) — the number of digits in the decimal representation of S and the maximum allowed number of changed digits.

The second line contains the integer S. It's guaranteed that SS has exactly n digits and doesn't contain any leading zeroes.

Output Specification:

Output the minimal possible value of S which Ania can end with. Note that the resulting integer should also have n digits.

Sample Input1:

5 3
51528

Sample Output1:

10028

Sample Input2:

3 2
102

Sample Output2:

100

Sample Input3:

1 1
1

Sample Output3:

0

Note:

A number has leading zeroes if it consists of at least two digits and its first digit is 0. For example, numbers 00, 00069 and 0101 have leading zeroes, while 0, 3000 and 1010 don't have leading zeroes.

解题思路：

题目大意就是给定一个n位数str，允许改变str上的k位，求能构成的最小的数是多少。分情况讨论：①若k=0说明str的一位数都不能改变，直接将str进行输出；②若n=1说明str只有个位数，直接将str置零进行输出；③n不为1且k不为0，先将str的第一位数置为1，然后再将剩下的位数全部置为0即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n,k;    //str的长度为n,允许改变str的k位数
    string str;
    cin >> n >> k >> str;
    if(!k)    //k=0说明str的一位都不能改变
    {
        cout << str << endl;
    }
    else if(n == 1)    //str只有个位数且k不为0则直接将str置零
    {
        cout << 0 << endl;
    }
    else
    {
        if(str[0] != '1')    //第一位数置1
        {
            str[0] = '1';
            k--;
        }
        Up(i,1,n-1)    //剩下的位全部置0
        {
            if(str[i]!='0' && k)
            {
                str[i] = '0';
                k--;
            }
        }
        cout << str << endl;
    }
    return 0;
}