UVA11020 Efficient Solutions

• 2022 年 7 月 9 日
• 筆記
• A題筆記, STL, 思維

題目鏈接

題目

見鏈接。

題解

知識點：STL，思維。

首先不考慮新加入的操作，先考慮一個固定的局面，給定了所有人的兩個屬性值 \(L\) 和 \(C\)，找出有競爭力的人。

這類雙變數的條件一般可以畫在坐標系 \(L-C\) 查看，發現如果一個點坐標到原點構成的矩形內部（包括邊，但不包括這個點本身）有其他點，則這個點就沒有競爭力。於是發現有競爭力人群規律，其中 \(L\) 小的人相對於其他人 \(C\) 會較大，而 \(L\) 大的人相對於其他人 \(C\) 會較小。因為對於一個 \(L\) 小的人，那麼後面 \(L\) 大的人 \(C\) 要比 \(L\) 小的人的 \(C\) 小，不然就沒競爭力，所以整體會呈現一個反比例函數的形式。因此對已有的人按 \(L\) 為第一關鍵字從小到大排， \(C\) 為第二關鍵字從小到大排。

現在考慮插入一個人，先找到 \(lower\_bound\)到 \(L\) 大或 \(L\) 等於但 \(C\) 大於等於的第一個點，那麼上一個點就是 \(L\) 小於他的最後一個點，則 \(C\) 要比上一個點的 \(C\) 嚴格小，才有資格插入。

隨後開始排除後面那些 \(L\) 大於等於他的人，但 \(C\) 大於他的人。先 \(upper\_bound\) 找到 \(L\) 大 或 \(L\) 等於且 \(C\) 大的第一個點，從這裡往後所有 \(C\) 小於等於他的 \(C\) 的人全都沒有競爭力了（因為 \(upper\_bound\) ，所以如果 \(L\) 相等只可能 \(C\) 比他大）。

每次插入後容器大小是有競爭力的人的人數。注意到容器要滿足排序，插入，刪除，查找，且元素可能重複，因此用 \(multiset\) 。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct node {
    int x, y;
    friend bool operator<(node a, node b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }
};

bool solve() {
    int n;
    cin >> n;
    multiset<node> ms;///畫x-y圖分析得出，有效點若按x從小到大，則y一定從大到小，且一個x點處，不可能有y不同的點
    for (int i = 0, x, y;i < n;i++) {
        cin >> x >> y;
        node a = { x,y };
        auto it = ms.lower_bound(a);///找到x大或x等於但y大於等於的第一個點，則上一個點一定是x小於的點
        if (it == ms.begin() || (--it)->y > y) {///這個點的y要比上一個點的y嚴格小,則有資格，開始踢後面的人
            ms.insert(a);
            it = ms.upper_bound(a);///找到x大 或 x等於且y大的第一個點
            while (it != ms.end() && it->y >= y) it = ms.erase(it);///往後這些點的x大於等於a的x，若y比a的y大於等於，就扔掉（x等於只有y大的情況）
        }
        cout << ms.size() << '\n';
    }

    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    int cnt = 1;
    while (t--) {
        cout << "Case #" << cnt++ << ":" << '\n';
        if (!solve()) cout << -1 << '\n';
        cout << (t ? "\n" : "");
    }
    return 0;
}