fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool isPossible(const vector<int>& v, int g, int k) {
  5.     int need = 0;
  6.     for (int x : v) {
  7.         if (x < g) need++;
  8.         else if (x % g == 0) continue;
  9.         else if (x >= 2 * g) continue;
  10.         else need++;
  11.         if (need > k) return false;
  12.     }
  13.     return need <= k;
  14. }
  15.  
  16. int main() {
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.  
  20.     int t;
  21.     cin >> t;
  22.     while (t--) {
  23.         int n, k;
  24.         cin >> n >> k;
  25.         vector<int> v(n);
  26.         for (int i = 0; i < n; i++) cin >> v[i];
  27.  
  28.         int lo = 1, hi = *max_element(v.begin(), v.end());
  29.         int ans = 1;
  30.  
  31.         while (lo <= hi) {
  32.             int mid = (lo + hi) / 2;
  33.             if (isPossible(v, mid, k)) {
  34.                 ans = mid;
  35.                 lo = mid + 1;
  36.             } else {
  37.                 hi = mid - 1;
  38.             }
  39.         }
  40.         cout << ans << "\n";
  41.     }
  42. }
  43.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6
9 1
4 9 6 8 2 6 7 8 2
10 1
4 9 6 8 2 6 7 8 2 7
7 5
1 1 2 3 4 5 5
7 4
1 1 2 3 4 5 5
14 3
14 12 7 12 9 9 12 4 3 1 3 6 9 13
1 0
1
stdout
copy 
2
2
2
2
3
1
https://ideone.com/G1FzXR
language:
C++14 (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!