# 【CSES】1090. Ferris Wheel

## [題目連結](https://cses.fi/problemset/task/1090/)

## **時間複雜度**

* $O(NlogN)$

## **解題想法**

這是一題有點小難的題目，要有想到 $NlogN$ 的作法才會過，我當初就是 $N^2$的做法卡超久才發現可以用 $NlogN$ 去處理QQ

### 解題關鍵

接下來敘述一下過這題的關鍵

**1. $NlogN$？**

因為題目的限制，每個座艙最多只能做兩個人，所以我就想到可以貪心抓重量和最接近限制的兩個人

抓第一個人的方法很簡單，致需要將數列排序之後從最大的開始慢慢往小的抓就可以了

但是抓第二個人的時候我們必須最快的在一個已經排序過後的陣列當中抓出跟第一位重量和最大同時小於限制的人，這時候一個熟悉的東西就出現了，就是**二分搜**

可是如果要使用官方的 `upper_bound()` 或是 `lower_bound()` 的話，必須將陣列由小排到大，但是這樣就不能從最前面開始抓第一個人了，所以這時候我就想到可以反向處理，**從尾巴開始往前抓**

**2. `visited[]`**

這題有可能會出現一個元素有多的人搶的問題，所以在實作的時候要記得加上 `visited` 陣列，以防一個元素被取很多次

**3. 人權圖**


## **完整程式**

/* Question : CSES 1090. Ferris Wheel */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;
int n, w, used, res, tmp, ind, point, last, arr[MAXN];
int visited[MAXN];

signed main(){
    opt;
    cin >> n >> w;
    for( int i = 0 ; i < n ; i++ ) cin >> arr[i];

    sort(arr, arr + n);
    
    mem(visited, false);
    ind = n-1;
    while( used < n ){
        tmp = w;
        tmp -= arr[ind];
        visited[ind] = true;
        if( tmp >= arr[0] ){
            int point = upper_bound(arr, arr+n-(n-ind), tmp) - arr;
            for( int i = point ; i >= 0 ; i-- ){
                if( visited[i] == true || tmp < arr[i] ) continue;
                visited[i] = true;
                used++;
                break;
            }
        }
        used++;
        ind--;
        res++;
    }

    cout << res << "\n";
}