Question

minlex[#2645]

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

Answer 1

#include <iostream>

#include <cstring>

using namespace std;

char s[1000001];

int k , vf , elim , st[1000001];

int main()

{

   cin >> k;

   cin.get();

   cin.getline(s , 1000000);

   int n = strlen(s);

   int i = 0;

   while(i < n)

   {

       if(vf == 0)

       {

           vf ++;

           st[vf] = int(s[i] - 'a' + 1);

       }

       else

       {

           while(st[vf] > int(s[i] - 'a' + 1) && elim < k && vf)

           {

               elim ++;

               vf --;

           }

           vf ++;

           st[vf] = int(s[i] - 'a' + 1);

       }

       i ++;

   }

   for(int i = 1 ; i <= n - k ; i ++)

       cout << char(st[i] - 1 + 'a');

   return 0;

}