290
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