2020牛客寒假算法基础集训营4.I——匹配星星【multiset 贪心 二分】

题目传送门

题目描述

注意：数据已加强(2020/02/12 14:40)
天上有n颗星星，每颗星星有二维坐标 $(x_i,y_i)$，还有一个属性值 $z_i$ ，若两颗星星A, B满足$x_A<x_B$ 且$y_A<y_B$ 且 $z_A<z_B$ ，则这两颗星星可以配成一对，每颗星星最多只能在一对之中，求最多能配成多少对星星。

输入描述:

第一行一个正整数 n ，表示星星的个数。
接下来 n 行，每行 3 个整数$x_i,y_i,z_i$ ，表示一颗星星。

输出描述:

一行一个整数，表示答案。

输入

2
1 1 0
2 2 1

2
1 1 1
2 2 1

输出

1

0

备注:

$1\le n\le 10^5$
$0\le x_i,y_i\le 10^9$
z i ∈ { 0 , 1 } z_i \in \{0, 1\} zi?∈{ 0,1}

题解

• 这道题目可以使用贪心算法求解。先按照X坐标从小到大排序，然后对于每一个点

1. 如果Z = 1，查询比他X坐标小的Y坐标最大的Z= 0的点，进行配对，如果配对成功则将那个点都从候选点中排除。
2. 如果Z = 0，将该点加入候选点。

• 证明
  假设最优方案中排序后$Z=1$的第 1 个没有按贪心策略匹配的点 $i$ ，在设 $i$ 在$Z=0$中它能匹配的 $y$ 最大的点为 $j$，如果 $j$ 被点 $k$ 匹配了，有两种情况：

1. 原先 i 没有和任何匹配，则直接去掉 k 的匹配，将 i 和 j 匹配。
2. 原先 i 和 m 匹配，则将 k 改成和 m 匹配，将 i 和 j 匹配，由于$Y_j>Y_m$， 这样的匹配一定是成立的。并且修改后的匹配数不会变少，因此按照该贪心策略可以得到最优解。
   

AC-Code

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
const int maxn = 1e5 + 7;struct Node {
    int x, y;bool z;bool operator < (Node t)const {
    if (x != t.x)	return x < t.x; // 只需对x排序即可，y和z不必须if (y != t.y)	return y < t.y; return z > t.z;}
}a[maxn];
int main() {
    int n;	while (cin >> n) {
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y >> a[i].z;sort(a, a + n);int ans = 0;multiset<int> pool;for (int i = 0; i < n; ++i) {
    if (a[i].z) {
    auto ite = pool.lower_bound(a[i].y); // 二分查找第一个大于等于当前点y值的。如果没有比y大的，返回last位置if (ite != pool.begin()) {
     // 如果不是begin，说明存在y比当前小的点--ite; // 找到比y小的里边，最大的pool.erase(ite);++ans;}}elsepool.insert(a[i].y); // 放入备选区}cout << ans << endl;}
}