fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int maxCards(int n, int k, const vector<int>& a) {
  9.     map<int, int> freq;
  10.     for (int num : a) {
  11.         freq[num]++;
  12.     }
  13.  
  14.     vector<pair<int, int>> sorted_freq(freq.begin(), freq.end());
  15.     int l = 0, total = 0, max_cards = 0;
  16.  
  17.     for (int r = 0; r < sorted_freq.size(); ++r) {
  18.         if (r > 0 && sorted_freq[r].first != sorted_freq[r - 1].first + 1) {
  19.             // Reset window if not consecutive
  20.             l = r;
  21.             total = 0;
  22.             for (int i = l; i <= r; ++i)
  23.                 total += sorted_freq[i].second;
  24.         } else {
  25.             total += sorted_freq[r].second;
  26.         }
  27.  
  28.         // Maintain at most k distinct numbers
  29.         while (r - l + 1 > k) {
  30.             total -= sorted_freq[l].second;
  31.             ++l;
  32.         }
  33.  
  34.         max_cards = max(max_cards, total);
  35.     }
  36.  
  37.     return max_cards;
  38. }
  39.  
  40. int main() {
  41.     int t;
  42.     cin >> t;
  43.     while (t--) {
  44.         int n, k;
  45.         cin >> n >> k;
  46.         vector<int> a(n);
  47.         for (int i = 0; i < n; ++i) cin >> a[i];
  48.         cout << maxCards(n, k, a) << endl;
  49.     }
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0s 5288KB
comments ()
stdin
copy 
4
10 2
5 2 4 3 4 3 4 5 3 2
5 1
10 11 10 11 10
9 3
4 5 4 4 6 5 4 4 6
3 2
1 3 1
stdout
copy 
6
3
9
2
https://ideone.com/sCJM96
language:
C++ (gcc 8.3)
created:
14 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!