Ferris Wheel

Ferris Wheel
CSES medium

There are \(n\) children who want to ride a Ferris wheel. Each gondola can hold one or two children, and the total weight in a gondola may not exceed \(x\). The weight of the \(i\)-th child is \(p_i\).

Find the minimum number of gondolas needed for all children.

Constraints:

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x \le 10^9\)
  • \(1 \le p_i \le x\)

Input:

  • First line: two integers \(n\) and \(x\) — the number of children and the maximum weight in a gondola.
  • Second line: \(n\) integers \(p_1, p_2, \dots, p_n\) — the weights of the children.

Output:

  • One integer — the minimum number of gondolas.

Example:

Input:

4 10
7 2 3 9

Output:

3
Solution

We sort the weights and look at the heaviest child who has no gondola yet. This child must get a gondola, and the best partner for this child is the lightest child who has no gondola yet:

  • If the lightest child fits together with the heaviest child, we put them in one gondola. Any other partner would be at least as heavy, so this choice cannot be worse.
  • If the lightest child does not fit, no other child fits either, so the heaviest child rides alone.

We implement this with two pointers on the sorted array: left points to the lightest child without a gondola, and right points to the heaviest one. Each step gives one gondola, moves right one position to the left, and moves left one position to the right if the two children ride together. The loop ends when the pointers cross.

Sorting takes \(O(n \log n)\) time and the loop takes \(O(n)\) time.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    sort(p.begin(), p.end());

    int left = 0;       // the lightest child without a gondola
    int right = n - 1;  // the heaviest child without a gondola
    int gondolas = 0;

    while (left <= right) {
        if (left < right && p[left] + p[right] <= x) {
            left++;  // the lightest child rides with the heaviest child
        }
        right--;
        gondolas++;
    }

    cout << gondolas << "\n";
}
CautionPitfalls
  • When left == right, only one child is left. The condition left < right stops us from pairing this child with itself.