12. 파라메트릭 서치

12.md

0.00MB

0. 복습
1. 파라메트릭 서치(이분탐색)

2805번을 보면,

f(h) : 높이를 h로 설정해서 자르면 얻는 나무의 양

이걸 높게 설정할수록 적게 얻고, 많이 설정할수록 많이 얻으니깐 항상 감소하는 모양이 나온다.

이걸 이진탐색으로 적절한 구간을 찾는다.

최대값의 최소, 최소값의 최대꼴이면 대부분 파라메트릭 서치를 활용할 수 있다.

#include <iostream>
using namespace std;
typedef long long int ll;
const int MN = 1000001;
int T[MN];
int N, M;

ll f(ll h){
    ll sum=0;
    for(int i=0; i<N; ++i){
        if(T[i] > h) sum+=T[i]-h;
    }
    return sum;
}
int main(){
    cin >> N >> M;
    for(int i=0; i<N; ++i){
        cin >> T[i];
    }

    int lo = 0, hi = 1e9 + 1;
    //lo는 가능, hi는 불가능.
    while(lo<hi-1){
        ll mid = (lo + hi)/2;
        if(f(mid)>=M) lo = mid;
        else hi=mid;
    }
    cout << lo << '\n';
}

연습 : 증가함수일때의 코드 짜보기.

참고 문제 : 2805, 2512, 1654, 1072

2. 볼록함수일 때의 파라메트릭 서치(삼분탐색)

감소하다 증가하는 함수일 때 사용.

8986번을 보자.

거리를 고정한다고 하면(삼분탐색으로 거리를 탐색)

f(x) : 간격을 x로 했을 때, 전봇대들의 이동 거리의 합.

f(x) = sigma(i=0 ~ N-1)( | i*X - arr[i] | )

즉, i=0일 때 |X - arr[i]|는 볼록함수이다. (뾰족함)

i=1일때도 마찬가지

i=N-1일때도 마찬가지.

볼록함수는 더해도 항상 볼록함수이기때문에 f(x)는 볼록함수이다.

기울기는 음수부터 증가하는 증가함수이기 때문에 이웃한 점의 기울기를 기준으로 탐색한다. (뾰족한점때문에 미분이 안되므로 각각 두 점 사이 거리를 구함)

#include <iostream>
using namespace std;
typedef long long int ll;
int N;
int arr[100001];

ll f(int X){
    ll sum=0;
    for(int i=0; i<N; ++i){
        sum += abs((ll)i*X - arr[i]);
    }
    return sum;
}

int main(){
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }
    int lo=1, hi=1000000001;
    while(lo<hi-1) {
        int mid = (lo + hi)/2;
        if(f(mid) - f(mid-1) < 0) lo = mid; // 기울기가 음수일때
        else hi=mid; // 기울기가 양수일 때
    }
    //cout << lo << ' ' << hi << ' ' << f(lo) << ' ' << f(hi) << '\n';
    cout << f(lo) << '\n'; //뾰족한 점의 f()를 출력
}

참고로 볼록함수들의 최대도 볼록함수다. 볼록다각형의 겹치는 부분도 볼록다각형이다. 그냥 참고만.

참고 : 8986, 9998