fbpx

Problema #2645 – minlex – Rezolvari PBInfo

de Mihai-Alexandru

Se consideră un cuvânt format numai din litere mici și un număr natural nenul K.

Cerința

Să se determine cuvântul minim lexicografic obținut prin eliminarea a exact K litere din cuvântul inițial.

Date de intrare

Programul citește de la tastatură numărul K, apoi cuvântul.

Date de ieșire

Programul va afișa pe ecran cuvântul rămas după eliminarea a exact K litere, minim lexicografic.

Restricții și precizări

  • 3 ≤ lungimea cuvântului ≤ 1.000.000
  • Cuvântul este format numai din litere mici ale alfabetului englez.
  • 1 ≤ K < lungimea cuvântului
  • Literele rămase după eliminare nu-și pot schimba ordinea în cuvânt.

Exemplu

Intrare

5 zyizxtnfo

Ieșire

info
#include <bits/stdc++.h>
using namespace std;

char s[1000001] , c[1000001];
int k , n;

int main()
{
    cin >> k >> c;
    n=1;
    s[n]=c[0];
    for(int i = 1 ; c[i] ; ++i)
    {
        while(n > 0 && c[i] < s[n] && k)
        {
            n--;
            k--;
        }
        n++;
        s[n]=c[i];
    }
    while(k)
    {
        n--;
        k--;
    }
    for(int i = 1 ; i <= n ; ++i)
        cout << s[i];
    return 0;
}
Comentarii

S-ar putea sa iti placa