【Codeforces】1230B – Ania and Minimizing

• 2019 年 11 月 8 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 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;  }