2821번: 컨베이어 벨트

https://www.acmicpc.net/problem/2821


볼록 껍질, 동적계획법


$O(n+m\lg n)$

si=sum(ti)라 하자.
자동차 fj와 fj+1 사이에 상근이가 쉬어야 할 시간은
임의의 i에 대해 d+si*fj+1>=si+1*fj 를 만족하는 최소 d 값이 된다.
이를 이용해서 주어진 j 마다 d를 빠르게 구하면 이 문제를 해결할 수 있다.
위 식을 다시 써보자.
d>= si+1*fj - si*fj+1
우변식은 Pi(si+1,si), Qi(fj, -fj+1) 두 점의 내적 결과라는 것을 알 수 있다.
이것의 의미(=d)는 원점과 Qi를 연결한 직선 위에 Pi를 정사영한 점과 원점까지의 거리로 해석할 수 있다.
Pi는 1사분면 위의 점이고 Qi는 4사분면 위의 점이다. Pi 점을 아무렇게 몇 개 찍어놓자.
또한 Pi들을 모두 포함하는 아래로 볼록한 볼록 껍질을 그려보자.
직관적으로 최소 d를 구하기 위해서는 주어진 Qi와 원점까지의 직선의 법선이 볼록 껍질과 접할 때의 그 pi를 이용하면 된다는 것을 알 수 있다.
이를 구하기 위해서는 법선의 기울기를 이용해 주어진 볼록껍질들을 이루는 선분의 기울기(오름차순)들 안에서 이진탐색을 이용해 최적화시키는 정점을 구하면 된다.

#include<stdio.h>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int MAX_N = 1e5, MAX_M = 1e5;
typedef long long ll;
int n, m, t[MAX_N], f[MAX_M], sz;
pair<ll, ll> p[MAX_N + 1];
double a[MAX_N];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", t + i);
    for (int i = 0; i < m; i++) scanf("%d", f + i);
    p[sz++] = { 0,0 };
    p[sz++] = { t[0],0 };
    ll s = t[0];
    for (int i = 1; i < n; i++) {
        while ((p[sz - 1].y - p[sz - 2].y)*(s + t[i] - p[sz - 1].x)>(s - p[sz - 1].y)*(p[sz - 1].x - p[sz - 2].x)) sz--;
        p[sz++] = { s + t[i],s };
        s += t[i];
    }
    ll res = s*f[m - 1];
    for (int i = 0; i < sz - 1; i++) a[i] = (double)(p[i + 1].y - p[i].y) / (p[i + 1].x - p[i].x);
    for (int i = 0, h; i < m - 1; i++) {
        h = upper_bound(a, a + sz - 1, (double)f[i] / f[i + 1]) - a;
        res += p[h].x*f[i] - p[h].y*f[i + 1];
    }
    printf("%lld", res);
    return 0;
}