fork download
copy 
  1. // kdel
  2. // https://v...content-available-to-author-only...e.com/op/view.aspx?src=http%3A%2F%2Fils.ntucoder.net%2Fckfinder%2Fuserfiles%2Ffiles%2F220813%2520-%2520De%2520bai.docx&wdOrigin=BROWSELINK
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. long long n, k, a[100009];
  7.  
  8. unordered_map<int, int> dem;
  9. multiset<int> ms;
  10.  
  11. int main() {
  12.     freopen("inp.txt", "rt", stdin);
  13.  
  14.     ios::sync_with_stdio(0);
  15.  
  16.     cin >> n >> k;
  17.     for (int i = 1; i <= n; i++) {
  18.         cin >> a[i];
  19.     }
  20.     int cnt = 0;
  21.  
  22.     int ans = 0;
  23.  
  24.     k++;
  25.     // bài toán tương đương: là tìm dãy con có k+1 loại phần tử khác nhau và xóa
  26.     // sau đó thống kê xem phần tử nào xuất hiện nhiều nhất
  27.     // 2 con trỏ cơ bản
  28.  
  29.  
  30.     for (int l = 1, r = 1; r <= n; r++) {
  31.         dem[a[r]]++;
  32.  
  33.         if (dem[a[r]] == 1) {
  34.             ms.insert(1); //multiset lưu số lần xuất hiện của từng loại ký tự/số
  35.         } else {
  36.             auto it = ms.find(dem[a[r]] - 1);
  37.             ms.insert(dem[a[r]]);
  38.             ms.erase(it);
  39.         }
  40.         while (dem.size() > k) {
  41.             auto it = dem.find(a[l]);
  42.             auto it1 = ms.find(it->second);
  43.  
  44.             it->second--;
  45.  
  46.             if (it->second == 0) {
  47.                 dem.erase(it);
  48.                 ms.erase(it1);
  49.             } else {
  50.                 ms.erase(it1);
  51.                 ms.insert(it->second);
  52.             }
  53.  
  54.             l++;
  55.         }
  56.  
  57.         ans = max(ans, *ms.rbegin());
  58.     }
  59.     std::cout << ans << endl;
  60. }
  61.  
Success #stdin #stdout 0.01s 5344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/D58GJD
language:
C++14 (clang 8.0)
created:
1 year 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!