Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <stdio.h>
- #include <algorithm>
- #include <list>
- std::string str;
- int c[30];
- std::list<int> char_pos[30];
- int get_high_char()
- {
- int res = 0;
- while(c[res] == 0) res++;
- for(int i = 0; i < 26; i++)
- {
- if(c[i] == 0) continue;
- if(c[res] < c[i]) res = i;
- }
- return res;
- }
- int get_lower_char()
- {
- int res = 0;
- while(c[res] == 0) res++;
- for(int i = 0; i < 26; i++)
- {
- if(c[i] == 0) continue;
- if(c[res] > c[i]) res = i;
- }
- return res;
- }
- int main()
- {
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- int n, k;
- std::cin >> n >> k;
- std::cin >> str;
- int g = std::min(n, k);
- for(int i = 0; i < n; i++)
- {
- c[str[i] - 'a']++;
- char_pos[str[i] - 'a'].push_front(i);
- }
- if(k >= n - c[get_high_char()])
- {
- int d = get_high_char();
- for(int i = 0; i < n; i++)
- {
- putchar('a' + d);
- }
- return 0;
- }
- for(int i = 0; i < g; i++)
- {
- int hi = get_high_char(), lo = get_lower_char();
- if(std::abs(c[hi] - c[lo]) == 0) break;
- int hi_pos = char_pos[hi].front();
- char_pos[hi].pop_front();
- char_pos[lo].push_front(hi_pos);
- str[hi_pos] = 'a' + lo;
- c[hi]--;
- c[lo]++;
- }
- std::cout << str << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment