메탈

메탈

Binary search


출처: BOJ 메탈

Sol)
 전형적인 이분법 문제라고 한다.
답이 될 수 있는 값을 이분법으로 찾는다.

[-] Collapse

#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

int n, k;
int ans;
pair<int, int> p[10000];
void search(int l, int r){
    if (l > r) return;
    int mid = (l + r) / 2;
    int temp_k = k-1;
    int mx, mn;
    mx = mn = p[0].second;
    for (int i = 1; i < n; i++){
        if (temp_k < 0) break;
        if (abs(mx - p[i].second) > mid || abs(mn - p[i].second) > mid){
            temp_k--;
            mx = mn = p[i].second;
            continue;
        }
        mx = max(mx, p[i].second);
        mn = min(mn, p[i].second);
    }
    if (temp_k < 0) search(mid + 1, r);
    else{
        ans = mid;
        search(l, mid - 1);
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &p[i].first, &p[i].second);
        sort(p, p + n);
        search(0, 200000000);
        if (ans & 1) printf("%d.5\n", ans / 2);
        else printf("%d.0\n", ans / 2);
    }
}