liohdi   1년 전

오션뷰(소형) 다국어

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
5 초 512 MB 435 269 228 61.957%
문제
오션뷰는 작은 호수 가장자리에 위치한 작은 마을로, 자존감이 높은 사람들이 거주하고 있습니다. 이 마을에는 서쪽의 호수에서 동쪽의 언덕으로 도망치는 어썸 블러바드라는 하나의 거리만 있습니다. 오션뷰의 모든 주택은 어썸 블러바드의 한쪽에 위치해 있으며, 호수 가장자리의 #1부터 언덕 기슭의 #N까지 번호가 매겨져 있습니다.

오션뷰의 각 거주자는 호수를 보기를 원합니다. 안타깝게도 일부 주택은 번호가 높은 일부 주택의 시야를 가리고 있을 수 있습니다. 집 #A는 집 #B가 B보다 작을 때마다 시야를 차단하지만, 집 #A는 집 #B만큼 크거나 높습니다.

방해된 전망에 대한 불만을 듣는 데 지친 오션뷰의 최고 통치자는 자신이 가장 좋아하는 통치 도구인 폭력을 사용하여 문제를 해결하기로 결정했습니다. 그는 남은 모든 집이 호수를 볼 수 있도록 하기 위해 경비원들에게 어썸 블러바드의 일부 집을 파괴하라고 명령할 것입니다. 물론 너무 많은 집을 파괴하면 반란이 일어날 수 있으므로 가능한 한 적은 집을 파괴하고 싶어합니다.

남아 있는 모든 집이 호수의 전망을 방해받지 않도록 하기 위해 파괴해야 하는 가장 적은 수의 집은 몇 채입니까?

입력
입력의 첫 번째 줄은 테스트 케이스의 수를 나타내며, T. T. 테스트 케이스는 다음과 같습니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 어썸 블러바드에 있는 주택 수인 단일 정수 N이 포함됩니다. 다음 줄에는 각 주택의 높이가 서쪽에서 동쪽으로 나열되며, 모든 양의 정수는 단일 공간으로 구분됩니다.

한계

1 ≤ T ≤ 100.
각 집의 높이는 포함하여 1에서 1000 사이가 될 것입니다.
1 ≤ N ≤ 50;
답은 항상 최대 4가 될 것입니다.
출력
각 테스트 케이스에 대해 "케이스 #x: y"를 포함하는 한 줄을 출력합니다. 여기서 x는 케이스 번호(1부터 시작)이고 y는 파괴해야 하는 최소 주택 수입니다.

예제 입력 1
4
4
1 4 3 3
5
3 4 6 7 10
4
4 3 2 1
5
4 5 6 1 7

예제 출력 1
사례 #1: 2
사례 #2: 0
사례 #3: 3
사례 #4: 1
힌트
예시 설명

사례 #1에는 몇 가지 가능한 해결책이 있습니다. 1번 집은 유지할 수 있지만 나머지 3채 중 2채는 파괴해야 합니다. 특히 3번 집은 4번 집의 시야를 계속 차단하기 때문에 가장 높은 집만 파괴하는 것만으로는 충분하지 않습니다.

사례 2는 파괴가 필요하지 않습니다. 모든 주민은 이미 호수를 볼 수 있습니다.

사례 #3은 절망적입니다. 우리는 집 중 하나를 제외한 모든 집을 파괴해야 합니다. 어느 집을 서 있든 상관없습니다.

#4의 경우, 가장 짧은 집의 거주자만이 자신의 시야 부족에 대해 불평하고 있습니다. 우리는 그의 서쪽에 있는 세 채의 집을 파괴할 수도 있지만, 대신 그의 집을 파괴하는 것이 나을 수도 있습니다. 그렇게 하면 그는 불평하지 않도록 배울 수 있을 것입니다.

댓글을 작성하려면 로그인해야 합니다.