👤

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


Răspuns :

#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;

}

Vă mulțumim că ați ales să vizitați site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți alte întrebări sau aveți nevoie de asistență suplimentară, nu ezitați să ne contactați. Vă așteptăm cu drag să reveniți și nu uitați să ne salvați în lista de favorite!


Ze Teaching: Alte intrebari