[백준]블록 쌓기(9998)

문제 링크 : [백준]블록 쌓기(9998)

9998번: 블록 쌓기

 

문제 설명

N칸에 걸쳐 블록을 임의의 높이로 두 줄이 쌓여있습니다.

두 줄의 블록을 가운데를 가장 낮게 하는 V자 형태로 변경하고 싶습니다.

쌓여있는 블록을 빼거나, 추가할 수 있는데, 이 행동을 가장 적게 수행하여 V자로 만드는 횟수를 구하세요.

 

입력

N(칸의 갯수, 1 <= N <= 300,000)

Y_i(첫 줄에 쌓인 각 칸의 블록 갯수, 0 <= Y_i <= 2¹²)

D_i(두번째 줄에 쌓인 각 칸의 블록 갯수, 0 <= D_i <= 2¹²)

3
1 2 3
3 2 2

 

출력

3

 

카테고리

#삼분탐색

 

시간 복잡도 상한

O(NlogM)(M은 블록 높이의 범위)

 

해결 방법

1. f(x)를 중앙의 높이가 x일 때, 이동해야 하는 블록의 수라고 정의하면, f(x)는 U자형 이차함수 그래프를 이룹니다.
   1. v를 구하고자 하는 최소값을 가질 때의 x라고 하면, x가 v보다 작거나, 크면 그때의 f(x)는 f(v)보다 커집니다.
2. 따라서 f(x)의 변곡점을 찾으면 됩니다.
3. 미분을 이용해도 되지만, 정확한 함수를 구하기 어렵기 때문에, 삼분탐색을 이용해서 풀 수 있습니다.
4. 결정 함수는 각 위치별 이동해야 하는 블록의 갯수들의 합입니다.
5. 다만 모든 값의 후보가 정수이기 때문에, 이분탐색을 하면서, f(x)와 f(x+1)의 값이 증가하는지 여부를 보고 답을 구할 수 있습니다.

시간복잡도

O(NlogM)(M은 블록 높이의 범위)

코드

#include<iostream>
#include<algorithm>
#define N 300000
using namespace std;
typedef long long L;
int n,i,c;
L s,l,r=1e12,m,a,b,d[N],e[N];
L x(int p,int o){
    return abs(d[c+p]-(m+o))+abs(e[c+p]-(m+o))+(p?abs(d[c-p]-(m+o))+abs(e[c-p]-(m+o)):0);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(c=n/2;i<n;i++)cin>>d[i];
    for(i=0;i<n;i++)cin>>e[i];
    while(l<=r){
        m=(l+r)/2;
        a=x(0,0);b=x(0,1);
        for(i=1;c+i<n;i++){
            a+=x(i,i);
            b+=x(i,i+1);
        }
        if(a<b)s=a,r=m-1;
        else s=b,l=m+1;
    }
    cout<<s;
}