Advertisement
AlejandroGY

Untitled

Apr 24th, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5.  
  6. struct por_contenido {
  7.     por_contenido(const std::string& sp)
  8.     : s(sp) {
  9.     }
  10.  
  11.     bool operator()(int i, int j) {
  12.         return s[i] < s[j];
  13.     }
  14.    
  15.     const std::string& s;
  16. };
  17.  
  18. int main( ) {
  19.     std::string s;
  20.     std::cin >> s;
  21.    
  22.     std::vector<int> mejor;
  23.     std::vector<int> padre(s.size( ), -1);
  24.    
  25.     for (int i = 0; i < s.size( ); ++i) {
  26.         if (mejor.empty( )) {
  27.             padre[i] = -1;
  28.             mejor.push_back(i);
  29.         }
  30.         else if (s[i] >= s[mejor.back( )]) {
  31.             padre[i] = mejor.back( );
  32.             mejor.push_back(i);
  33.         }
  34.         else {
  35.             std::vector<int>::iterator cambiar = std::lower_bound(mejor.begin( ), mejor.end( ), i, por_contenido(s));
  36.  
  37.             padre[i] = (cambiar == mejor.begin( ) ? -1 : *(cambiar - 1));
  38.             *cambiar = i;
  39.         }
  40.     }
  41.     std::cout << 26 - mejor.size( );
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement