SHARE
TWEET

Untitled

a guest Sep 20th, 2019 96 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define eb emplace_back
  6. #define mk make_pair
  7. #define fi first
  8. #define sec second
  9. #define fori(i, a, b) for(int i = int(a); i < int(b); i++)
  10. #define cc(x)   cout << #x << " = " << x << endl
  11. #define ok      cout << "ok" << endl
  12.  
  13. typedef pair<int,int> ii;
  14. typedef long long ll;
  15. const int INF = 0x3f3f3f3f;
  16. const double PI = acos(-1.0);
  17.  
  18. const int N = 1e5 + 10;
  19. ll n, c, cows[N];
  20.  
  21. bool check(int x, int c, int n){
  22.     int first = cows[0];
  23.     int cont = 1;
  24.  
  25.     for(int i = 1; i < n; i++){
  26.         if(cows[i] - first >= x){
  27.             first = cows[i];
  28.             cont++;
  29.  
  30.             if(cont == c) break;
  31.         }
  32.     }
  33.  
  34.     if(cont == c) return true;
  35.     else return false;
  36. }
  37.  
  38. int busca(int ini, int fim, int c, int n){
  39.     while(ini <= fim){
  40.         int mid = (ini+fim)/2;
  41.  
  42.         if(check(mid, c, n)) ini = mid+1;
  43.         else fim = mid-1;
  44.     }
  45.     return ini-1;
  46. }
  47.  
  48. int main(){
  49.     ios_base::sync_with_stdio(false);
  50.    
  51.     int tc; cin >>tc;
  52.     while(tc--){
  53.         cin >>n >>c;
  54.  
  55.         for(int i = 0; i < n; i++)
  56.             cin >>cows[i];
  57.    
  58.         sort(cows, cows+n);
  59.         cout <<busca(cows[0], cows[n-1], c, n) <<endl;
  60.     }
  61.     return 0;
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top