7983번: 내일 할거야

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


$O(n\lg n)$

끝내야 하는 시각을 기준으로 오름차순 정렬해놓자.
s[i]=d[0]+d[1]+...+d[i] 라고 하면
답은 min(t[i]-s[i]) 이다.

이를 증명해보자.
먼저, 해가 존재할 때 위처럼 빨리 끝내야 하는 과제부터 처리하면 항상 가능함을 보이자.
가능한 해를 보았을 때,
i<j이고 t[i]>t[j]인 i, j가 있다면 두 과제의 처리 순서를 바꿔도 된다.
처음 먼저 처리한 과제를 a, 나중에 처리한 과제를 b라 하면
당연히 a는 제한 조건이 더 까다로운 b가 해결했던 시각까지 과제를 마무리 할 수 있고
b 또한 s[j-1]-s[i-1] 만큼의 시간을 벌게 되므로 당연히 과제를 마무리 할 수 있기 때문이다.

최소값 y를 만드는 i=x라 하면
처음 y시간 만큼 쉬고 빨리 끝내야 하는 과제부터 처리하면 과제를 마무리 할 수 있는 것은 자명하다.
처음에 y보다 큰 시간을 쉬면 i번 과제를 해결할 수 없으므로 y가 가장 많이 쉴 수 있는 시간이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, r = 1e9, s;
pair<int, int> p[1000000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].second, &p[i].first);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        s += p[i].second;
        r = min(r, p[i].first - s);
    }
    printf("%d", r);
    return 0;
}