Ferris Wheel

題目

有 $n$ 個小孩想要搭摩天輪，你的任務是為每一位小孩找到他要搭的車廂。

每個車廂中只能有一個或兩個小孩，並且車廂中的載重不能超過 $x$。你知道每個小孩的重量。

請問最少需要多少的車廂才能讓所有小孩都能搭上摩天輪？

輸入

• 第一行有兩個整數 $n$ 和 $x$，分別代表小孩數量與車廂載重限制。（$1 \le n \le 2 \cdot 10^5$，$1 \le x \le 10^9$）
• 第二行有 $n$ 個整數 $p_i$，分別代表各個小孩的重量。（$1 \le p_i \le x$）

輸出

輸出最少需要多少車廂。

範例測資

Input:
4 10
7 2 3 9

Output:
3

第一個車廂載 $2$ 和 $7$ （$2+7 \le 10$）

第二個車廂載 $3$

第三個車廂載 $9$

想法

用貪心的策略去思考。如果目前最重的小孩與最輕的小孩總重量大於車廂載重限制 $x$，就讓最重的小孩獨自搭乘一個車廂；否則就讓最重的小孩與最輕的小孩共乘一個車廂。按照這個策略不斷地分配車廂，直到所有小孩都搭上車廂為止。如此一來必定是最佳的（花費最少車廂的）分配法。

「讓最重的小孩與最輕的小孩共乘」是最佳策略的證明

為了證明按照上面的策略產生的分配法是最佳的，我們要說明它花費的車廂數輛不會比任何最佳分配法還要多。為了方便說明，我們將小孩編號依體重由輕到重排序為 $c_1, \ldots, c_n$，並且將各自的體重表示為 $\bar{p}_i = p_{c_i}$，也就是說有 $\bar{p}_i \le \bar{p}_{i+1}$。

首先，若 $\bar{p}_1 + \bar{p}_n > x$，那麼對任何 $i$ 也都會有 $\bar{p}_i + \bar{p}_n > x$，表示這時體重最重的 $c_n$ 在任何分配法下都無法與其他小孩 $c_i$ 共乘而必須獨自搭乘一個車廂。這時按照我們的策略來分配車廂並不會比任何最佳分配法還要差。

假設 $\bar{p}_1 + \bar{p}_n \le x$，代表最輕的 $c_1$ 可以與最重的 $c_n$ 共乘而不超出車廂載重限制。假設 $\mathcal{F}$ 是一個最佳的分配法。我們知道至少有一個車廂是兩人共乘的，否則我們就能讓 $c_1$ 與 $c_n$ 共乘來製造出花費車廂數更少的分配法而產生矛盾。

若想要嚴格定義分配法 $\mathcal{F}$，假設 $R$ 為所有小孩的集合，我們可以把 $\mathcal{F}$ 定義為 $R$ 的分割，並使任意的 $G \in \mathcal{F}$ 都滿足 $|G| \le 2$。也就是說 $\mathcal{F}$ 的元素是兩兩不相交的非空集合 $G \subseteq R$，各自代表一個車廂。

如果在分配法 $\mathcal{F}$ 中最輕的 $c_1$ 沒有與任何小孩共乘，那我們可以將任意一個共乘車廂中的任意一個小孩與 $c_1$ 交換，製造出另一個分配法 $\mathcal{F}^\ast$。因為車廂數量不變，分配法 $\mathcal{F}^\ast$ 必定也是最佳分配法。所以不妨假設 $\mathcal{F}$ 中的 $c_1$ 已經與某個小孩共乘了，那麼我們會有三種情況：

1. 最輕的 $c_1$ 恰好與最重的 $c_n$ 共乘。
2. 最輕的 $c_1$ 與 $c_k$ 共乘，而最重的 $c_n$ 沒有與任何小孩共乘。那我們直接將 $c_k$ 與 $c_n$ 交換就可製造出一個 $c_1$ 與 $c_n$ 共乘的最佳分配法。
3. 最輕的 $c_1$ 與 $c_k$ 共乘，而最重的 $c_n$ 與 $c_j$ 共乘。因為 $\bar{p}_j + \bar{p}_k \le \bar{p}_j + \bar{p}_n \le x$，可知 $c_k$ 也可與 $c_j$ 共乘而不超出車廂載重限制。那麼我們一樣可以直接將 $c_k$ 與 $c_n$ 交換來製造出一個 $c_1$ 與 $c_n$ 共乘的最佳分配法。

所以總會有個最佳分配法跟我們的策略一樣是讓 $c_1$ 與 $c_n$ 共乘的，表示這時按照我們的策略來分配車廂也一樣不會比任何最佳分配法還要差。

按照同樣的策略不斷對剩下的小孩分配車廂，因為總是不比最佳分配法差，於是這個策略也會製造出一個最佳分配法。

範例程式碼

C++ 範例

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

int main() {
    int n, m;
    int arr[200005];
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);

    int l = 0, ans = 0;
    for(int r = n-1; r >= l; r--) {
        if(arr[l] + arr[r] <= m) {
            l++;
        }
        ans++;
    }
    cout << ans;
}