2911 전화 복구

2911 전화 복구 https://www.acmicpc.net/problem/2911

전화감지기가 $N$개, 일열로 된 집이 $M$개 있다.
전화감지기가 $P_{i}$와 $P_{i + 1}$의 중간에 위치할 때 동쪽과 서쪽에서 통화한것을 감지할 수 있다.
전화감지기의 위치와 해당 통화량이 주어질 때 하루동안 감지된 최소한의 통화량을 구하는 문제다.

다음과 같은 예를 들어보자. ('/'는 감지기의 위치)
$N = 3, M = 5$
1 / 2 3 4 5 : 1통화
1 2 / 3 4 5 : 2통화
1 2 3 / 4 5 : 2통화

첫번째를 보면 1번집과 2,3,4,5번 집 사이의 통화가 한번은 존재한다.
두 번째에서 2통화가 되었는데 이것은 2번집과 3,4,5번 집 사이에 한통화가 존재한다는 뜻이다.
(1번집과 2,3,4,5번 집 사이의 통화가 한번 있었기 때문)
세 번째에서도 여전히 2통화인데 이를 통해서 얻을 수 있는 확실한 정보는 없게된다.

따라서 주어진 입력을 감지기 위치 순으로 오름차순 정렬 후 증가하는 것에대해 누적합하면 된다.

#include <cstdio> #include <algorithm> using namespace std; int N, M; pair<int, int> call[100001]; int main() {     scanf("%d%d", &N, &M);     for (int n = 0;n < N;n++) {         scanf("%d%d", &call[n].first, &call[n].second);     }     sort(call, call + N);     long long ans = 0;     long long prev = 0;     for (int n = 0;n < N;n++) {         if (prev < call[n].second) {             ans += (long long)(call[n].second - prev);         }         prev = call[n].second;     }     printf("%lld\n", ans);     return 0; } Colored by Color Scripter

cs

이런 추상적인 문제 참 좋은 문제인것 같다.