BAEKJOON 3020 - FIREFLY

문제: https://www.acmicpc.net/problem/3020

문제

A Japanese firefly has flown into a cave full of obstacles: stalagmites (rising from the floor) and stalactites (hanging from the ceiling). The cave is N units long (where N is even) and H units high. The first obstacle is a stalagmite after which stalactites and stalagmites alternate. 

Here is an example cave 14 units long and 5 units high (the image corresponds to the example): 

The Japanese firefly is not the type that would fly around the obstacle, instead it will choose a single height and ram from one end of the cave to the other destroying all obstacles in its path with its mighty kung-fu moves. 

In the previous example, choosing the 4th level from the ground has the firefly destroying eight obstacles: 

This is not the best choice because the firefly will end up less tired if it chooses either level one or five, as that would require destroying only seven obstacles. 

You are given the width and length of the cave and the sizes of all obstacles. 

Write a program that determines the minimum number of obstacles the firefly needs to destroy to reach the end of the cave, and on how many distinct levels it can achieve that number. 

입력

The first line contains two integers N and H, 2 ≤ N ≤ 200000, 2 ≤ H ≤ 500000, the length and height of the cave. N will always be even. 

The next N lines contain the sizes of the obstacles, one per line. All sizes are positive integers less than H. 

출력

Output two integers separated by a single space on a single line. The first number is the minimum number of obstacles the firefly has to destroy and the second is the number of levels on which that can be achieved. 

예제 입력 

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 

7 2

힌트

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Croatian Regional Competition in Informatics 2007 3번

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Regional Competition - Juniors 4번

이진 탐색으로 풀 방법이 딱히 생각나지 않아 정렬로 풀어봤습니다. 각 높이의 입력을 받아 count 를 한 후 부딫칠 수 있는 개수를 구하기 위해 각 크기보다 더 큰 장애물의 합을 모두 더한 후 각 높이에 따른 장애물의 수를 구한 후 정렬을 해서 풀었습니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
using namespace std;
 
int main()
{
    int n, h, num;
    scanf("%d %d", &n, &h);
    vector<int> bottom(h + 1, 0);
    vector<int> top(h + 1, 0);
    vector<int> sorted(h, 0);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        if (i % 2 == 0)
            bottom[num]++;
        else
            top[num]++;
    }
    for (int i = h - 1; i > 1; i--)
    {
        bottom[i - 1] += bottom[i];
        top[i - 1] += top[i];
    }
 
    for (int i = 1; i <= h; i++)
        sorted[i - 1] = bottom[i] + top[h - i + 1];
 
    sort(sorted.begin(), sorted.end());
 
    int count = 1;
    for (int i = 1; i < h; i++)
    {
        if (sorted[0] == sorted[i])
            count++;
        else
            break;
    }
    printf("%d %d\n", sorted[0], count);
    return 0;
}