Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <string>
- #include <vector>
- struct por_contenido {
- por_contenido(const std::string& sp)
- : s(sp) {
- }
- bool operator()(int i, int j) {
- return s[i] < s[j];
- }
- const std::string& s;
- };
- int main( ) {
- std::string s;
- std::cin >> s;
- std::vector<int> mejor;
- std::vector<int> padre(s.size( ), -1);
- for (int i = 0; i < s.size( ); ++i) {
- if (mejor.empty( )) {
- padre[i] = -1;
- mejor.push_back(i);
- }
- else if (s[i] >= s[mejor.back( )]) {
- padre[i] = mejor.back( );
- mejor.push_back(i);
- }
- else {
- std::vector<int>::iterator cambiar = std::lower_bound(mejor.begin( ), mejor.end( ), i, por_contenido(s));
- padre[i] = (cambiar == mejor.begin( ) ? -1 : *(cambiar - 1));
- *cambiar = i;
- }
- }
- std::cout << 26 - mejor.size( );
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement