o1-mini-2024-09-12· OpenAI WildChat-4.8M (AI2)
Cows to the stalls Input file: stdin Output file: stdout Time limit: 1 sec Memory limit:…
- User
Cows to the stalls Input file: stdin
Output file: stdout
Time limit: 1 sec
Memory limit: 256 mb
On the straight line there are stalls in which you have to arrange the cows so that the minimum distance between the cows is as large as possible.
Input The first line contains N (2<N≤105) – the number of stalls and K (1<K<N) – the number of cows. The second line contains N natural numbers in ascending order – the coordinates of the stalls (the coordinates do not exceed 109 ).
Output One number – the largest possible allowable distance.
Examples Input 1:
copy
6 3 2 5 7 11 15 20
Output 1:
copy
9
Input 2:
copy
5 3 1 2 3 100 1000
Output 2:
copy
99 solve in c++. do not use comments. use short naming. use bits/std...
- Assistant
#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N,K; cin>>N>>K; vector<int>A(N); for(auto &x:A) cin>>x; auto possible = [&](int d)->bool{ int cnt=1, last=A[0]; for(int i=1;i<N;i++) if(A[i]-last>=d){cnt++; last=A[i]; if(cnt>=K) return true;} return cnt>=K; }; int l=0, r=A[N-1]-A[0], res=0; while(l<=r){ int m = l + (r-l)/2; if(possible(m)){res=m; l=m+1;} else r=m-1; } cout<<res; }