fork download
copy 
  1. #include<bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. void solve() {
  7.     int n, k;
  8.     cin >> n >> k;
  9.  
  10.     int a[n]; 
  11.     map<int, int> m;
  12.  
  13.     for(int i = 0; i < n; i++) {
  14.         cin >> a[i];
  15.         m[a[i]]++;
  16.     }
  17.  
  18.     vector<int> v;
  19.  
  20.     for(auto it : m) {
  21.         v.push_back(it.second);
  22.     }
  23.  
  24.     sort(v.begin(), v.end());
  25.  
  26.     int ans = 0;
  27.     int i = v.size() - 1;
  28.  
  29.     for(; i >= 0; i--) {
  30.         if(v[i] >= k) {
  31.             v[i] = 0;
  32.             if(i - 1 >= 0) v[i - 1] += k - 1;
  33.             else if (i == 0) ans = k - 1;
  34.         }
  35.         else break;
  36.     }
  37.  
  38.     while(i >= 0) {
  39.         ans += v[i];
  40.         i--;
  41.     }
  42.  
  43.     cout << ans << endl;
  44. }
  45.  
  46. int32_t main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.  
  50.     int t;
  51.     cin >> t;
  52.  
  53.     while(t--) {
  54.         solve();
  55.     }
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
7
5 3
4 1 1 4 4
1 10
7
7 2
4 2 1 100 5 2 3
10 4
1 1 1 1 1 1 1 1 1 1
5 2
3 8 1 48 7
6 2
10 20 30 10 20 40
6 3
10 20 30 10 20 40
stdout
copy 
2
1
1
3
5
1
6
https://ideone.com/O1cYG1
language:
C++ 4.3.2 (gcc-4.3.2)
created:
17 days 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!