Guest User

t1z3_version1

a guest
Jan 11th, 2017
358
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <stdio.h>
  4. #include <algorithm>
  5. #include <list>
  6.  
  7. std::string str;
  8. int c[30];
  9. std::list<int> char_pos[30];
  10.  
  11. int get_high_char()
  12. {
  13.     int res = 0;
  14.     while(c[res] == 0) res++;
  15.     for(int i = 0; i < 26; i++)
  16.     {
  17.         if(c[i] == 0) continue;
  18.         if(c[res] < c[i]) res = i;
  19.     }
  20.     return res;
  21. }
  22.  
  23. int get_lower_char()
  24. {
  25.     int res = 0;
  26.     while(c[res] == 0) res++;
  27.     for(int i = 0; i < 26; i++)
  28.     {
  29.         if(c[i] == 0) continue;
  30.         if(c[res] > c[i]) res = i;
  31.     }
  32.     return res;
  33. }
  34.  
  35. int main()
  36. {
  37.     freopen("input.txt", "rt", stdin);
  38.     freopen("output.txt", "wt", stdout);
  39.    
  40.     int n, k;
  41.     std::cin >> n >> k;
  42.     std::cin >> str;
  43.    
  44.     int g = std::min(n, k);
  45.     for(int i = 0; i < n; i++)
  46.     {
  47.         c[str[i] - 'a']++;
  48.         char_pos[str[i] - 'a'].push_front(i);
  49.     }
  50.    
  51.     if(k >= n - c[get_high_char()])
  52.     {
  53.         int d = get_high_char();
  54.         for(int i = 0; i < n; i++)
  55.         {
  56.             putchar('a' + d);
  57.         }
  58.         return 0;
  59.     }
  60.    
  61.     for(int i = 0; i < g; i++)
  62.     {
  63.         int hi = get_high_char(), lo = get_lower_char();
  64.        
  65.         if(std::abs(c[hi] - c[lo]) == 0) break;
  66.        
  67.         int hi_pos = char_pos[hi].front();
  68.         char_pos[hi].pop_front();
  69.         char_pos[lo].push_front(hi_pos);
  70.        
  71.         str[hi_pos] = 'a' + lo;
  72.        
  73.         c[hi]--;
  74.         c[lo]++;
  75.     }
  76.    
  77.     std::cout << str << std::endl;
  78.    
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment