[C++] [CSES] Ferris Wheel (Sorting and Searching)

CSES Sorting and Searching 세번째 문제입니다.

곤돌라에는 한명이나 두명이 탈 수 있습니다. 어린이들을 모두 태우는 데 필요한 곤돌라의 최소 개수를 출력하는 문제입니다.

 

Task

 

There are n children who want to go to a Ferris wheel, and your task is to find a gondola for each child.

Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed x. You know the weight of every child.

What is the minimum number of gondolas needed for the children?

Input

The first input line contains two integers n and x: the number of children and the maximum allowed weight.

The next line contains n integers p1,p2,…,pn: the weight of each child.

Output

Print one integer: the minimum number of gondolas.

Constraints

• 1≤n≤2⋅1e5
• 1≤x≤1e9
• 1≤pi≤x1

Example

Input:
4 10
7 2 3 9

Output:
3

 

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, x, ans;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> x;
    vector<int> ar(n);
    for (int i=0;i<n;i++) cin >> ar[i];
    sort(ar.begin(), ar.end());

    int l = 0, r = n - 1;
    while (l <= r){
        if (ar[l] + ar[r] <= x){
            l++; r--;
        }
        else r--;
        ans++;
    }
    cout << ans;
}

생각해야 하는 것

• 정렬을 통해서 문제를 그리디하게 풀 수 있습니다.
• 가장 무거운 친구부터 태운 다음, 현재 가장 가벼운 친구를 태울 수 있다면 추가하고, 그렇지 않으면 추가하지 않습니다.
• 만약 중간부터 두번째 친구를 태울 수 있으면 그 친구를 태우는 것이 더 그리디할 것 같다는 생각을 했지만, 정렬된 배열의 non-decreasing한 특성, 문제에서 두명만 태울 수 있다는 조건을 생각해본다면 --> 매번 그 중간사람을 찾는 것은 배열을 한번 돌아야 하기 때문에 효율적이지 못하고, 코드에 적힌 방법을 써도 최소 곤돌라의 개수를 구할 수 있음을 알 수 있습니다.