CSES – Ferris Wheel

題目連結

題意

有 n 個小孩想要搭摩天輪，第 i 個小孩的重量用 p[i] 表示。每個摩天輪車廂可以載一個或兩個小孩，最大負重量是 x (可以是 x 可是不能超過)。問最少需要幾個車廂就可以讓全部的小孩都搭到摩天輪。

解題方法

將 p 陣列從小到大排序，每次嘗試把還沒配對到的最重的小孩配上最輕的小孩。
利用兩個指針l和r分別從最左邊 (最小) 及 最右邊 (最大) 開始模擬
重量超出限制的話就讓比較重的小孩自己一個，沒超出的話就將兩個配對在一起。

原因:
如果最重 + 最輕已經超出限制的話，最重的小孩不管再配誰都也會超出限制 (越後面的小孩只會越來越重)，所以在這邊我們可以確定那個小孩一定要自己一車。

#include <bits/stdc++.h>
using namespace std;
int main(){    
    int n, x;
    cin >> n >> x;
    vector <int> p(n);
    for(int &t : p) cin >> t;
    sort(p.begin(), p.end());
    int ans = 0;
    int l = 0, r = n-1;
    while(l <= r){
        if(p[l]+p[r] > x) { //超出重量限制
            r--; // 重的小孩自己一車
        } else { // 沒超出重量限制
            l++,r--; 
        }
        ans++;
    }
    cout << ans << '\n';
}