CodeForces - 999C Alphabetic Removals

Lokinli

发布于 2023-03-09 16:06:22

2660

发布于 2023-03-09 16:06:22

文章被收录于专栏：以终为始

C - Alphabetic Removals

You are given a string

consisting of lowercase Latin letters. Polycarp wants to remove exactly characters ( ) from the string . Polycarp uses the following algorithm times:

if there is at least one letter 'a', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
if there is at least one letter 'b', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
...
remove the leftmost occurrence of the letter 'z' and stop the algorithm.

This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly times, thus removing exactly characters.

Help Polycarp find the resulting string.

Input

The first line of input contains two integers and () — the length of the string and the number of letters Polycarp will remove.

The second line contains the string consisting of lowercase Latin letters.

Output

Print the string that will be obtained from after Polycarp removes exactly letters using the above algorithm times.

If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break).

Examples

Input

15 3
cccaabababaccbc

Output

cccbbabaccbc

Input

15 9
cccaabababaccbc

Output

cccccc

Input

1 1
u

Output

这个题就是给你一个已知长度的字符串，给你一个数k，要求要从这里面删去k个字符，删去的这k个字符要求是从a开始删除，如果a没有删完，那么就不能删除b，依次进行，直到删完k个字符就可以了。

#include <bits/stdc++.h>

using namespace std;

char s[400005];
int a[1000];  // a用来标记每个字母出现的次数
int main()
{
    int n, k;
    while(~scanf("%d %d",&n, &k))
    {
        getchar();
        memset(a, 0,sizeof(a));
        for(int i = 0; i < n; i ++)
        {
            scanf("%c",&s[i]);
            a[s[i]] ++;
        }
        if(k >= n) printf("\n");  //如果需要删除的k大于n，就全部删除没了
        else
        {
            int num = 0;
            for(int i = 97; ; i ++) // 从a开始删除，如果满足k>=a[i],把所有的字符都删去即可
            {
                if(k >= a[i])
                {
                    num ++;
                    k = k - a[i];
                }   
                else break;
            }
            for(int i = 0; i < n; i ++)
            {

                if(s[i] < 97 + num);  //删除掉的不再输出
                else
                {
                    if(s[i] == 97 + num)  // 没有全部删除完成，继续删除这个字符
                    {
                        if(k > 0)k--;
                        else printf("%c",s[i]);
                    }
                    else printf("%c",s[i]); // 输出不需要删除的
                }

            }
            printf("\n");
        }
    }
    return 0;
}

发现可以省去好多代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
char str[400005];

int main()
{
  cin>>n>>m;
  cin>>str;
  for(int i=0;i<=25;i++){
    for(int j=0;j<n&&m;j++){
      if(str[j] == 'a' + i){
        str[j] = '0';
        m--;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(str[i] != '0')cout<<str[i];
  }
  return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-07-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度