Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define eb emplace_back
- #define mk make_pair
- #define fi first
- #define sec second
- #define fori(i, a, b) for(int i = int(a); i < int(b); i++)
- #define cc(x) cout << #x << " = " << x << endl
- #define ok cout << "ok" << endl
- typedef pair<int,int> ii;
- typedef long long ll;
- const int INF = 0x3f3f3f3f;
- const double PI = acos(-1.0);
- const int N = 1e5 + 10;
- ll n, c, cows[N];
- bool check(int x, int c, int n){
- int first = cows[0];
- int cont = 1;
- for(int i = 1; i < n; i++){
- if(cows[i] - first >= x){
- first = cows[i];
- cont++;
- if(cont == c) break;
- }
- }
- if(cont == c) return true;
- else return false;
- }
- int busca(int ini, int fim, int c, int n){
- while(ini <= fim){
- int mid = (ini+fim)/2;
- if(check(mid, c, n)) ini = mid+1;
- else fim = mid-1;
- }
- return ini-1;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- int tc; cin >>tc;
- while(tc--){
- cin >>n >>c;
- for(int i = 0; i < n; i++)
- cin >>cows[i];
- sort(cows, cows+n);
- cout <<busca(cows[0], cows[n-1], c, n) <<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement