fork(3) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. static const int N = (int)1e6;
  5. static const int INF = (int)1e9;
  6.  
  7. int n, k;
  8. char s[N + 2], t[N + 2];
  9. int cnt[26], p[26];
  10. int ans[26], ans_size;
  11. int cur[26];
  12.  
  13. bool comp(const int &x, const int &y) {
  14.     return cnt[x] < cnt[y];
  15. }
  16.  
  17. int main() {
  18.     freopen("input.txt", "rt", stdin);
  19.     freopen("output.txt", "wt", stdout);
  20.  
  21.     scanf("%d%d\n%s", &n, &k, s);
  22.  
  23.     k = std::min(n, k);
  24.  
  25.     for (int i = 0; i < n; i++)
  26.         cnt[s[i] - 'a']++;
  27.  
  28.     for (int i = 0; i < 26; i++)
  29.         p[i] = i;
  30.  
  31.     std::sort(p, p + 26, comp);
  32.  
  33.     ans_size = INF;
  34.  
  35.     for (int i = 0, sum = 0; i < 26; i++) {
  36.         if (sum > k)
  37.             break;
  38.  
  39.         for (int j = i; j < 26; j++)
  40.             cur[j] = cnt[p[j]];
  41.  
  42.         for (int j = 0; j < i; j++) {
  43.             for (int k = 0; k < cnt[p[j]]; k++) {
  44.                 int p = i;
  45.  
  46.                 for (int l = i; l < 26; l++)
  47.                     if (cur[l] < cur[p])
  48.                         p = l;
  49.  
  50.                 cur[p]++;
  51.             }
  52.         }
  53.  
  54.         for (int j = sum; j < k; j++) {
  55.             int pl = i, ph = i;
  56.  
  57.             for (int k = i; k < 26; k++) {
  58.                 if (cur[k] < cur[pl])
  59.                     pl = k;
  60.                 if (cur[k] > cur[ph])
  61.                     ph = k;
  62.             }
  63.  
  64.             if (cur[pl] < cur[ph])
  65.                 cur[pl]++, cur[ph]--;
  66.         }
  67.  
  68.         int pl = 0, ph = 0;
  69.  
  70.         for (int j = 0; j < 26; j++) {
  71.             if (cur[j] > 0 && (cur[pl] == 0 || cur[j] < cur[pl]))
  72.                 pl = j;
  73.  
  74.             if (cur[j] > 0 && (cur[ph] == 0 || cur[j] > cur[ph]))
  75.                 ph = j;
  76.         }
  77.  
  78.         if (cur[ph] - cur[pl] < ans_size)
  79.         {
  80.             ans_size = cur[ph] - cur[pl];
  81.  
  82.             for (int j = 0; j < 26; j++)
  83.                 ans[p[j]] = cur[j];
  84.         }
  85.  
  86.         sum += cnt[p[i]], cur[i] = 0;
  87.     }
  88.  
  89.     for (int i = 0; i < 26; i++) {
  90.         for (int j = 0; j < n && ans[i] > 0; j++)
  91.             if (t[j] == 0 && s[j] == i + 'a')
  92.                 t[j] = i + 'a', ans[i]--;
  93.     }
  94.  
  95.     for (int i = 0; i < 26; i++) {
  96.         for (int j = 0; j < n && ans[i] > 0; j++)
  97.             if (t[j] == 0)
  98.                 t[j] = i + 'a', ans[i]--;
  99.     }
  100.  
  101.     printf("%s", t);
  102.  
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0s 5420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HLNhbq
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!