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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema minlex:

#include <bits/stdc++.h>
#define nmax 1000005
using namespace std;

char a[nmax];
int k;
char s[nmax];

int main()
{
    int i, top;
    char x;
    cin >> k;
    cin >> (s + 1);
    a[0] = 'A';
    top = 0;
    for (i = 1; s[i] && k > 0; ++i)
    {
        x = s[i];
        while (k > 0 && a[top] > x)
        {
            k--;
            top--;
        }
        a[++top] = x;
    }
    for( ; s[i]; i++)
        a[++top] = s[i];
    while (k > 0)
    {
        k--;
        top--;
    }
    a[top + 1] = 0;
    cout << (a + 1) << "\n";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2645 minlex

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2645 minlex de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2645 minlex