CSES - Ferris Wheel

Solution

Unofficial Editorial

Since each gondola can contain either 1 or 2 children, for each gondola, we can either

1. pair the lightest child with the heaviest child possible without exceeding the weight limit; if pairing isn't possible, we
2. only include the lightest child.

Those left unpaired each get their own gondola. The implementation below uses this method.

Alternatively, for each gondola, we can either

1. pair the heaviest child with the lightest child if possible; or
2. only include the heaviest child.

Both pairing methods can be achieved in $\mathcal{O}(n)$ time using two pointers, though sorting is more expensive.

Overall Time Complexity: $\mathcal{O}(n\log n)$ (from sorting)

#include <bits/stdc++.h>

using namespace std;

//constant initialization
const int maxn=2e5+10;
 
//variables used for the current problem
int n,x,p[maxn],i,j,ans; 
bool have_gondola_yet[maxn]; //A boolean array which counts the number of children who have had their own bondola