专栏首页Don的成长史【Codeforces】1230B - Ania and Minimizing

【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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单词首字母大写

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

    喜欢ctrl的cxk
  • 【CCF】二十四点

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

    喜欢ctrl的cxk
  • A+B

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

    喜欢ctrl的cxk
  • PHP对Json字符串解码返回NULL的一般解决方案

    php对json字符串解码使用json_decode()函数,第一个参数传字符串,第二个参数若为true,返回array;若为false,返回object。如果...

    用户7657330
  • 【leetcode刷题】T90-转换成小写字母

    实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。

    木又AI帮
  • 金额转大写

    在处理财务账款时,需要将转账金额写成大写的。也就是说,如果要转账123456.00元,则需要写成“壹拾贰万叁仟肆佰伍拾陆元整”。 所以常常需要通过程序控制自动进...

    崔笑颜
  • C#字符串截取

    yaphetsfang
  • Python过滤不可见字符

        for i in range(0,32):         str = str.replace(chr(i),'')

    py3study
  • php字符串和0比较,比较都默认转换为0? 原

    if($str==0),字符串和数字比较是否相等, 相当于 把$str 字符串隐性转换为数字,然后再比较,相当于 if( intval($str) == 0 )...

    lilugirl
  • python学习总结五(python序列

    成员关系符就是判断一个字符是否属于这个字符串,再就是这个字符串是否属于这个元组,或者列表。返回值也是布尔值(True,Flase)。

    py3study

扫码关注云+社区

领取腾讯云代金券