8014 : 페리스 바퀴
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
놀이공원에 $N$명의 아이들이 페리스 바퀴를 타기 위해 대기하고 있습니다. 각 곤돌라에는 최대 2명까지 탑승할 수 있으며, 탑승한 아이들의 몸무게 합은 최대 $X$ 이하여야 합니다.
모든 아이들을 태우기 위해 필요한 최소 곤돌라 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le X \le 10^9$
• $1 \le p_i \le X$ (각 아이의 몸무게)
모든 아이들을 태우기 위해 필요한 최소 곤돌라 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le X \le 10^9$
• $1 \le p_i \le X$ (각 아이의 몸무게)
입력 설명
첫째 줄에 두 정수 $N$과 $X$가 공백으로 구분되어 주어집니다.
둘째 줄에 각 아이의 몸무게 $p_1, p_2, \ldots, p_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 아이의 몸무게 $p_1, p_2, \ldots, p_N$이 공백으로 구분되어 주어집니다.
출력 설명
필요한 최소 곤돌라 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 10
7 2 3 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
몸무게 배열을 오름차순으로 정렬한 뒤 투 포인터를 사용합니다.
가장 무거운 아이와 가장 가벼운 아이의 합이 $X$ 이하이면 두 명을 한 곤돌라에 태우고, 초과하면 가장 무거운 아이 혼자 곤돌라 하나를 타도록 그리디하게 배정합니다.
가장 무거운 아이와 가장 가벼운 아이의 합이 $X$ 이하이면 두 명을 한 곤돌라에 태우고, 초과하면 가장 무거운 아이 혼자 곤돌라 하나를 타도록 그리디하게 배정합니다.