fork download 
  1. #include<bits/stdc++.h>
  2. #define fst ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL);
  3. #define ll long long 
  4. #define endl '\n'
  5. using namespace std;
  6. int main(){
  7.     fst
  8.     int t;
  9.     cin >> t;
  10.     while(t--){
  11.         int n;
  12.         cin >> n;
  13.         vector<int> a(n);
  14.         for(int i=0;i<n;i++) cin >> a[i];
  15.         sort(a.begin(),a.end());
  16.         auto ok = [&](int mid){
  17.             map<int,int> mp;
  18.             int cnt = 0, m = 0, tmp = n, k = 0;
  19.             for(int i=0;i<n;i++) mp[a[i]]++;
  20.             for(int i=1;i<=mid;i++){
  21.                 int res = mid - i + 1;
  22.                 if(cnt > 0 && mp[res] > 0){
  23.                     cnt=0;
  24.                     mp[a[k]]--;
  25.                     if(mp[a[k]] == 0) k++;
  26.                 }
  27.                 if(mp[res] > 0 && cnt == 0){
  28.                     m++;
  29.                     mp[res]--;
  30.                     tmp--;
  31.                     if(tmp == 0) break;
  32.                     else cnt++;
  33.                 }
  34.                 else {
  35.                     int r = 0;
  36.                     for(int j=n-1;j>=0;j--){
  37.                         if(a[j] <= res && cnt > 0 && mp[a[j]] > 0){
  38.                             cnt = 0;
  39.                             mp[a[k]]--;
  40.                             if(mp[a[k]] == 0) k++;
  41.                         }
  42.                         else if(cnt == 0 && a[j] <= res && mp[a[j]] > 0){
  43.                             r = a[j];
  44.                             break;
  45.                         }
  46.                     }
  47.                     if(r && mp[r] > 0){
  48.                         m++;
  49.                         mp[r]--;
  50.                         tmp--;
  51.                         if(tmp == 0) break;
  52.                         else cnt++;
  53.                     }
  54.                     else break;
  55.                 }
  56.             }
  57.             return m == mid;
  58.         };
  59.         int l=1,r=100,mid,ans=0;
  60.         while(l <= r){
  61.             mid = (l + r) / 2;
  62.             if(ok(mid)){
  63.                 ans = mid;
  64.                 l = mid + 1;
  65.             }
  66.             else r = mid - 1;
  67.         }
  68.         cout << ans << endl;
  69.     }
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
4
3
1 1 2
4
4 4 4 4
1
1
5
1 3 2 1 1
stdout 
2
0
1
3
https://ideone.com/cBAzIc
language:
C++14 (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!