Ferris wheel

Abridged problem statement

Given an array $a$ and an integer $x$, partition the elements of $a$ into as few groups as possible. Each group may contain at most two elements, and the sum of its elements must not exceed $x$. Determine the minimum number of groups.

Solution

Note: we use the same technique introduced in this article, which may be considered a prerequisite.

Once again, let us employ the extremal principle. Given $a$, assuming $|a| > 1$, consider $m=\min\{a\}$ and $M=\max\{a\}$.

If $m+M > x$, we are forced to create a separate group for $M$—it cannot pair with any other element if it can’t pair with the smallest!

If $m+M \le x$, must we pair $M$ with $m$?

Consider the contrary—that is—consider the case when $M$ is paired with some other element $e$. We have two subcases:

Case #1: $m$ is unpaired

(symmetric to $M$ is unpaired, which has been omitted)

In this case, we can simply replace $e$ with $m$, keeping the number of groups the same.

Case #2: $m$ is paired with some other $f$

We know that $M+e \le x$ (turns out we don’t even need to use $m+f \le x$).

Since $m \le e$ and $M+e \le x$, $M+m \le x$ as well. But is $e+f \le x$?

Yes, because $e+M \le x$ and $f \le M$ implies $e+f \le x$.

So, yes, pairing $m$ with $M$ really just works. This may seem somewhat magical at first, but we’re actually doing almost the exact same thing as in apartments.

Implementation

We maintain a pointer at the front and back.

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int &i : a) {
    cin >> i;
  }
  
  sort(a.begin(), a.end());
  int i = 0, j = a.size() - 1;
  int ans = 0;
  while (i <= j) {
    ans++;
    if (a[i] + a[j] <= x) {
      i++, j--;
    } else {
      j--;
    }
  }

  cout << ans << '\n';
}