fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool can_form_k_sets(int x, int k, unordered_map<int, int>& freq) {
  5.     int sets = INT_MAX;
  6.     for (int i = 0; i < x; ++i) {
  7.         sets = min(sets, freq[i]); // each number i in 0..x-1 must appear at least once per set
  8.     }
  9.     return sets >= k;
  10. }
  11.  
  12. int main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.  
  16.     int t;
  17.     cin >> t;
  18.  
  19.     while (t--) {
  20.         int n, k;
  21.         cin >> n >> k;
  22.         vector<int> a(n);
  23.         unordered_map<int, int> freq;
  24.         for (int i = 0; i < n; ++i) {
  25.             cin >> a[i];
  26.             freq[a[i]]++;
  27.         }
  28.  
  29.         int low = 0, high = n, ans = 0;
  30.  
  31.         while (low <= high) {
  32.             int mid = (low + high) / 2;
  33.             if (can_form_k_sets(mid, k, freq)) {
  34.                 ans = mid;        // try higher
  35.                 low = mid + 1;
  36.             } else {
  37.                 high = mid - 1;   // too much, try lower
  38.             }
  39.         }
  40.  
  41.         cout << ans << '\n';
  42.     }
  43.  
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
7
1 1
0
5 1
0 1 3 2 4
6 2
2 1 0 0 1 2
5 5
0 0 0 0 0
5 2
2 3 4 5 6
6 2
0 0 1 1 2 2
4 4
1 0 0 0
stdout
copy 
1
5
3
1
0
3
0
https://ideone.com/7AVuq7
language:
C++ (gcc 8.3)
created:
4 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!