BAPC 2014 Final

题库链接戳这里

E. Excellent Engineers

题意：有n个工程师，取三个技能来衡量工程师的水平。现在给你每个工程师这三个技能在这N人中的排名r1、r2、r3，不存在同名的情况。问：哪些工程师可能是最优秀的？这些可能是最优秀的工程师会出现在候选人名单上，问候选人名单上有多少个人？以数据为例子：

3       |    3
2 3 2   |    1 2 3
3 2 3   |    2 3 1
1 1 1   |    3 1 2

第1组，显然第3人三项技能的排名都是1，故而他是唯一候选人无疑，解为1。第2组里，每个人都有一项技能排名第1，其它虽然排名不及别人，但是不确定在能力上究竟差多少，于是，3个人都有可能是最强的，于是解为3。

这道题挺有意思的。一开始想的是如果工程师A各项技能都强于工程师B，那么建立一条单向边，最后求的是有多少个连通块。但是n范围是1e5，这个复杂度n^2，不可行。解决办法比较巧妙，复杂度是nlogn。
解法思路：先把工程师按r3的情况，从小到大排序。从前到后遍历这个序列，这样会使得对于当前工程师而言，往后的人不会在r3上比自己优秀。在此基础之上，新考虑的人虽然技能3不如前面的人，但是如果技能2是最优秀的，或者说，技能2不是最优秀的，但是技能1，比那些技能2、3都比自己优秀的人优秀，也加入候选人名单。

在技能3有序的情况下，技能1和技能2的分布情况是一个二维图：

中间图的e是新加入的点，虽然因为晚入，技能3略逊，技能1也不是最好的，但是他比技能1比他好的人技能2好，比技能2比他好的人技能1好，故亦入选。我们在下面的算法中，用一个set来维护这样一条链。这条链的意义是：边界。即那些在x或y维度有所突破的人，会成为候选人。为什么一定会成为候选人呢？因为他对于前面的人而言，已经有所突破，他整体实力也许不比前面的人弱，又他比后面的人先考虑，于是技能3强于往后的人，后面的人技能1、2再强，他也可能不比他们弱，于是是否最强不可断定，入候选人集合。
代码里实现稍不一样：先排序r1，然后以r2和r3来模拟上面这样的二维图。之前没接触过这种题(菜)，觉得很巧妙。啰嗦一下，因为名次无同名，所以it1表示的是技能2比E[i]弱的人，it2则表示的是技能比E[i]强的人，要去比较该人和E[i]的技能3情况。

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

#define lowb lower_bound
const int maxN = 1e5 + 5;
int N, M, K, T;

struct Engineer {
    int r1, r2, r3;
    Engineer() {}
    Engineer(int a, int b, int c)
        : r1(a), r2(b), r3(c) {}
};

bool cmp1(Engineer &a, Engineer &b) { return a.r1 < b.r1; }
struct cmp2 {
    bool operator() (Engineer a, Engineer b) {
        return a.r2 < b.r2;
    }
};

Engineer E[maxN];
set<Engineer, cmp2> S;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i = 0; i < N; ++i)
            scanf("%d%d%d", &E[i].r1, &E[i].r2, &E[i].r3);

        sort(E, E + N, cmp1);
        int ans = 1;
        S.clear();
        S.insert(E[0]);

        set<Engineer>::iterator it, it1, it2;
        for (int i = 1; i < N; ++i) {
            it1 = S.lowb(E[i]);
            it2 = it1;
            it2--;
            if (it1 == S.begin() || E[i].r3 < it2->r3) {
                ++ans;
                for (it = it1; it != S.end() && E[i].r3 < it->r3;)
                    S.erase(it++);
                S.insert(E[i]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}