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;
}