gshscs

매서운 겨울이 지나가고, FJ는 농장의 울타리를 다시 페인트칠하기로 했다. 농장은 모든 성분이 x축과 y축에 평행한 직사각형으로 되어 있는 N개(1 <= N <= 50,000)의 구역으로 나뉘어져 있다. 모든 구역은 울타리로 경계를 표시한다. 어떤 구역이 다른 구역 안에 포함될 수 있지만, 두 구역의 경계가 서로 겹치지는 않는다.

다른 구역 안에 포함되어 있는 구역은 밖에서 볼 수 없기 때문에, FJ는 다른 어떤 구역에도 포함되지 않는 구역만 칠하려고 한다. FJ가 칠해야 하는 구역의 수를 구하는 프로그램을 만드시오.

PROBLEM NAME : painting

INPUT FORMAT

Line 1 : 구역의 수 N이 주어진다.

Line 2~N+1 : 각 직사각형 구역의 정보 x1, y1, x2, y2가 주어진다. (x1, y1)은 구역의 왼쪽 아래 점, (x2, y2)는 구역의 오른쪽 위 점을 나타낸다. 모든 정보는 0과 1,000,000사이의 정수이다.

OUTPUT FORMAT

Line 1 : 다른 어떤 구역에도 포함되지 않는 구역의 수를 구한다.

SAMPLE INPUT

3 2 0 8 9 10 2 11 3 4 2 6 5

SAMPLE OUTPUT

2

http://www.usaco.org/index.php?page=viewproblem2&cpid=263

여러가지 해법들이 있지만, O(N)의 시간 안에 답을 구할 수 있는 간단한 그리디 알고리즘을 소개하겠다.
최소 실행 수는 a[i]와 a[i-1], a[i+1]의 차이의 합의 절반과 같다는 것에 주목할 필요가 있다. 왜 그런지는 잘 생각해보자.

a[i]-a[i-1]은 i등급부터 straight가 시작되는 수를 나타낸다. a[i]와 a[i+1]의 경우에서도 마찬가지이다. 따라서 최소 실행 수는 abs(a[i+1]-a[i])의 합에서 2로 나눈 값이다.

Bessie와 친구들은 1부터 N(1 <= N <= 100,000)까지 등급이 매겨진 카드를 가지고 특이한 방식의 포커를 하고 있다(보통은 N = 13). 게임 방식은 간단하다. i부터 j까지 등급의 카드가 한 개씩 있으면 “straight”라고 하고, 그 카드들은 없앤다.

Bessie는 i등급의 카드를 a_i개씩 가지고 있다. 모든 카드를 없애기 위해서 필요한 최소 실행 수를 구하여라.

PROBLEM NAME : poker

INPUT FORMAT

Line 1 : 정수 N이 주어진다.

Line 2~N+1 : i등급의 카드의 개수 a_i가 주어진다.

OUTPUT FORMAT

Line 1 : 모든 카드를 없애기 위해서 필요한 최소의 실행 수를 출력한다.

SAMPLE INPUT

5 2 4 1 2 3

SAMPLE OUTPUT

6

http://www.usaco.org/index.php?page=viewproblem2&cpid=262