https://www.acmicpc.net/problem/23875
23875번: Closest Cow Wins
Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are $K$ grassy patches ($1 \leq K \leq 2\cdot 10^5$); the $i$-th patch is located at position $p_i$ and has an associat
www.acmicpc.net
풀이 방향조차 몰라서 솔루션 깐 문제
Nhoj의 소들 위치로 전체 구간을 M+1개의 구간으로 나눈다.
모든 구간은 소 2마리로 John이 다 먹을 수 있다. (양 끝 구간은 1마리만으로 먹기 가능)
만약 어떤 구간에 John이 소 1마리만 두는 경우 그 소의 위치를 x라 해보자.
그러면 John은 ((f[i] + x) / 2, (f[i + 1] + x) / 2) 구간을 다 먹을 수 있다.
구간의 길이는 항상 (f[i + 1] - f[i]) / 2 이므로 슬라이딩 윈도우로 최대값을 미리 저장해둘 수 있다.
모든 구간에 소를 한 마리씩만 둘 수 있다고 생각해보자. 그러면 M+1개의 구간 중에서 큰 순서대로 N개를 고르면 된다.
이제 소를 두 마리 둘 수 있는 경우를 생각해보자.
소를 한 번에 두 마리 다 넣는게 아닌 한 마리 넣고 다시 추가로 한 마리를 넣는다고 생각해보면
두 번째 소가 먹는 양은 그 구간 전체 - 한 마리가 이미 먹은 양 이다.
따라서 양 끝 구간을 제외한 모든 구간에서 one, all - one을 구해서 내림차순으로 정렬하고 (양 끝 구간은 one만)
N개를 고르면 된다.
이 때, 같은 구간에서의 one과 all - one은 정렬 시 항상 one이 앞에 와야 한다.