Article From:https://www.cnblogs.com/buerdepepeqi/p/9216842.html
C. Alphabetic Removals
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string ss consisting of nn lowercase Latin letters. Polycarp wants to remove exactly kk characters (knk≤n) from the string ss. Polycarp uses the following algorithm kk 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 kk times, thus removing exactly kk characters.

Help Polycarp find the resulting string.

Input

The first line of input contains two integers nn and kk (1kn41051≤k≤n≤4⋅105) — the length of the string and the number of letters Polycarp will remove.

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

Output

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

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

Examples
input

Copy
15 3
cccaabababaccbc
output

Copy
cccbbabaccbc
input

Copy
15 9
cccaabababaccbc
output

 
cccccc
input

 
1 1
u
output

u
 
Meaning: to give you a string, you can do the K operation on this string, each operation follows this rule: delete from a, delete the A and delete the B… All the time to Z
Answer: use an array to save the number of each letter in a string, then delete it from a, record the location that can’t be deleted, and save the output with another string.
The code is as follows

#include<bits/stdc++.h>
using namespace std;
int n;
string str;
int k;
vector<int> cnt(26);
int main() {


    cin>>n>>k;
    cin>>str;

    for(int i=0; i<n; i++) {
        cnt[str[i]-'a']++;
    }
    //Record the number of each letter//Start subtracting the existing letters from a//If not, record the letters that can be output.
    int pos=26;
    for(int i=0; i<26; i++) {
        if(k>=cnt[i]) {
            k-=cnt[i];
        } else {
            pos=i;
            break;
        }
    }

    string ans;
    int rem=k;
    for(int i=0; i<n; i++) {
        int cur=str[i]-'a';
        //The letters behind POS can be used//Using the letters of K can be used
        
        if(cur>pos||(cur==pos&&rem==0)) {
            ans+=str[i];
        } else if(cur==pos) {
            rem--;
        }
    }
    cout<<ans<<endl;

    return 0;
}

View Code

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *