SHARE
TWEET

Untitled

a guest Sep 20th, 2019 81 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) return true;
  31.         }
  32.     }
  33.     return false;
  34. }
  35.  
  36. int busca(int ini, int fim, int c, int n){
  37.     while(ini <= fim){
  38.         int mid = (ini+fim)/2;
  39.  
  40.         if(check(mid, c, n)) ini = mid+1;
  41.         else fim = mid-1;
  42.     }
  43.     return ini-1;
  44. }
  45.  
  46. int main(){
  47.     ios_base::sync_with_stdio(false);
  48.    
  49.     int tc; cin >>tc;
  50.     while(tc--){
  51.         cin >>n >>c;
  52.  
  53.         for(int i = 0; i < n; i++)
  54.             cin >>cows[i];
  55.    
  56.         sort(cows, cows+n);
  57.         cout <<busca(cows[0], cows[n-1], c, n) <<endl;
  58.     }
  59.     return 0;
  60. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top