백준 20917 사회적 거리 두기

http://www.acmicpc.net/problem/20917 

20917번: 사회적 거리 두기

이분탐색을 통해 푸는 문제였습니다.

N개중에 S개를 고르고 S개 사이의 거리중 가장 짧은 거리가 최대가 되는 값을 구하는 문제였습니다.

이분탐색에서 mid를 답이 될 수 있는지 체크하는 함수를 만드는게 문제에서 큰 부분이었고 이는 N개를 정렬한후 시작이나 끝으로 부터 시작해 mid값을 더하거나 빼나가며 그 더하거나 뺀값보다 좌석이 같거나 멀리있을때 그 좌석은 포함될 수 있습니다. 따라서 포함될수 있는 좌석의 개수가 S개보다 크거나 같을 경우 그 mid값은 답이 될 수 있습니다.

#include <stdio.h>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int T;
int arr[200001];
int N,S;
bool chk(int a){
    auto e=arr+N;
    int cnt=0;
    auto now=arr;
    while(now!=e){
        now=lower_bound(now,arr+N,*now+a);
        cnt++;
    }
    if(cnt>=S) return true;
    else return false;
}
int main(){
    fast_io();
    cin>>T;
    while(T--){
        cin>>N>>S;
        for(int x=0;x<N;x++) cin>>arr[x];
        sort(arr,arr+N);
        int l=1;
        int r=arr[N-1]-arr[0];
        int ans=1;
        while(l<=r){
            int mid=(l+r)/2;
            if(chk(mid)){
                l=mid+1;
                ans=max(ans,mid);
            }
            else r=mid-1;
        }
        cout<<ans<<'\n';
    }
}