DARPA Grand Challenge

https://algospot.com/judge/problem/read/DARPA

비슷한 문제 : https://hsdevelopment.tistory.com/548

파라매트릭 서치(Parametric Search) Greedy 그리디 탐색 복습 필수 추천 코테 코딩

계속 오답이길래 봤더니 이분 탐색 시작점(s)을 1로 했었다.

답이 0인 경우도 있는 것 같다.

#include<bits/stdc++.h>
 
using namespace std;
 
int n, m;
 
bool chk(const vector<double> &v, double mid)
{
    int cnt = 0;
    double bf = v[0];
 
    for (int i = 1; i < v.size(); i++) {
        if (v[i] - bf >= mid) {
            ++cnt;
            bf = v[i];
        }
    }
 
    return cnt >= n - 1;
}
 
double bt(const vector<double> &v, double s, double e)
{
    double ret = 0;
 
    for (int i = 0; i < 100; i++) {
        double mid = (s + e) / 2.0;
 
        if (chk(v, mid)) {
            //ret = max(ret, mid);
            s = mid;
        }
        else {
            e = mid;
        }
    }
 
    return s; //ret도 가능
}
 
int main()
{
    cin.tie(0);
 
    int t;
    scanf("%d", &t);
    for (int tc = 0; tc < t; tc++) {
        vector<double> v;
 
        scanf("%d %d", &n, &m);
        
        double input;
        for (int i = 0; i < m; i++) {
            scanf("%lf", &input);
            v.push_back(input);
        }
 
        // printf("%.2lf\n", bt(v, 1, v[m - 1]));
        printf("%.2lf\n", bt(v, 0, v[m - 1]));
    }
 
    return 0;
}