[ALGOSPOT]DARPA

파라메트릭 서치 포스팅하려다가 도저히 말로 못풀어쓰겠는데

그래도 문제를 풀 수 있을 것 같아서 

15년 (2.....년전) 10월에 누군가가 내줬던 문제를 풀었다.

그 당시 이분탐색은 안다 그런데 이건 이분탐색이라고? 물어봤었던 기억이 난다.

이거 어떻게 풀어 못풀겠어 하고...... 1년 반이 지났다...

그리고서 BOJ에서 문제를 쪼끔..... 풀다보니 이게 파라메트릭 서치라는 거는 알았는데

이렇게 하면 되겠다? 하는데 이걸 말로 풀어쓰지를 못하겠다.

일단...

레이스 길이가 있고, 놓아야할 카메라 수 n 개가 있다.

그리고 카메라를 놓을 수 있는 자리 m개가 있다.

이때 카메라를 놓을 수 있는 자리 m개의 각 위치가 오름차순으로 주어지고!

카메라는 n개를 m개 자리에 무조건 놓아야 한다. 

그런데 카메라들을 m개 자리에 모두 배치했을 때 제일 가까운 거리가 최대가 되는 값을 출력해라!

라는 문제이다.

이분 탐색을 하는데 카메라 사이의 길이를 이분탐색한다. 최대 길이는 0부터 가장 마지막 v[m-1] 일 것이다. 

그렇다면 이때 최대가 될 수 있는 값은 [ 0 , v[m-1] ] 이 사이에 있는데 이걸 어떻게 구할거니?

라는 문제가 되고

이분탐색에서 카메라 사이의 길이를 어떻게 찾아갈래? 라고 물어본다면, 

카메라 사이의 길이를 조건으로 하여 길이를 늘리던지 줄이던지 해야한다. 

근데 그 카메라 사이 길이는 지점마다 배치를 두었을 때 

n개의 카메라를 두어야 한다.

그런데 처음부터 v[0] 번째 부터 카메라를 배치해서 찾아가는 것이 무조건 최적이라는 것은 당연한 거니까

v[0] 부터 카메라를 두고 다음 카메라를 둘 위치를 찾아간다.

카메라를 두었다면 batch 값을 ++ 해서 카메라 하나 두었음! 두개 두었음! 한다.

다음 카메라를 두기 위해서! 해야 할 작업으로.. 

n 개를 배치해야하는데 n개 보다 많은 수의 카메라를 배치 했다면? 

카메라 사이 길이를 늘여야 한다. 그래야 n개보다 많은 수 배치한 카메라 수를 줄일 수 있을테니까

n 개를 배치해야하는데 n개 보다 적은 수의 카메라가 배치 됐다면?

카메라 사이 길이를 줄여야 한다. 카메라는 무조건 n개 배치되어야 하므로...

그런데? n개를 배치할 수 있어! 그럼 이 길이가 최적이야 이걸 return 해! 

하면 안된다. 

n개를 배치하는 것이 최적이 아니라 

이 문제에서 제일 가까운 거리가 최대가 되는 것을 출력하는 문제이니까..

n개를 배치 할 수 있다면? 길이를 더 늘여봐야한다.

이 과정을 반복하면 된다..

#include<cstdio>
#include<vector>
using namespace std;
typedef int type;
vector<type> v;
int n;
int m;
int parametric_condition(type leng){
    int ret = 0;
    int batch = 0;
    type set_batch = 0;
    for(int i = 0 ; i < m ; i++){
        if(i == 0){
            batch++;
            set_batch = v[0];
        }
        else if(v[i] - set_batch >= leng){
            batch++;
            set_batch = v[i];
        }
    }
 
    if(batch >= n){ // more batch, leng increase
        return 1;
    }else if(batch < n){ // less batch, leng decrease
        return -1;
    }
    return 0;
}
 
type round(type data){
    type ret = int(data*100)/100.0;
    if(data - ret > 0.005001) ret += 0.01;
    return ret;
}
type floorr(type data){
    type ret = int(data*100)/100.0;
    return ret;
}
type parametric_search(){
    type start = 0;
    type end = v[m-1];
    type mid;
    while(start < end){
        //start = round(start);
        //end = round(end);
        mid = (start+end)/2;
 
        if(start == end) return mid;
        switch(parametric_condition(mid)){
        case -1: // batch < n
            end = mid-1;
            break;        
        case 1: // batch > n
            start = mid+1;
            break;
        }
        
    }
    return mid;
}
 
int main(){
    int tc;
    for(scanf("%d", &tc) ; tc-- ; ){
        scanf("%d%d",&n,&m);
        v.resize(m);
        for(int i = 0 ; i < m ; i++){
            float temp;
            scanf("%f",&temp);
            v[i] = temp*10000;
        }
        printf("%.2f\n",(parametric_search()/10000.0));
    }
    return 0;
}