CSES 2. Ferris Wheel (1090)

출처: https://cses.fi/problemset/task/1090

---

문제 설명

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 xx. You know the weight of every child.

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

입력 

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 p_1,p_2,…,p_n: the weight of each child.

출력

Print one integer: the minimum number of gondolas.

입력 예

4 10
7 2 3 9

출력 예

3

제약조건

• 1 <= n <= 2x1e5  
• 1 <= x <= 1e9 
• 1 <= p_i <= x

---

문제 풀이

무게를 입력받아서 정렬하고, 앞쪽(left)와 뒤쪽(right) 아이의 몸무게를 합쳐서 제한무게와 비교한다.

작으면, 곤돌라 하나에 탑승시키고(left+1, right-1), 무거우면 무거운 아이 혼자 타도록 한다.(right-1)  

프로그램 내용

...
    int nChild, weightL;
    cin >> nChild >> weightL ;

    long childWeight[nChild] = {0};

    for (int in=0; in < nChild; ++in)
        cin >> childWeight[in];

    sort(childWeight, childWeight+nChild);

    int idx=0, id = nChild-1;
    int gondola_count=0;

    while( idx <= id )
        if (childWeight[idx] + childWeight[id] > weightL) id--;
        else { idx++; id--;}
        gondola_count++;

	cout << gondola_count << endl;

 

Sorting and Searching ( link )