Solve

C++ STL中平衡树在算法题目的应用

题目描述•其一

给定一个长度为n的数组s，数组s的子串s[i,j]表示s[i],s[i+1],s[i+2]……s[j]。求最大长度的子串，该子串必须满足：m1<=max(s[i],s[i+1]……s[j])-min(s[i],s[i+1]……s[j])<=m2。如果最大长度的子串有多个，请找出子串和最大的那个。对于子串[i,j]，子串和指的是sum(s)=s[i]+s[i+1]+s[i+2]+……s[j]，子串长度指的是length=j-i+1。如果没有子串满足，请输出”0 0”。

样例

第一行为三个整数n, m1, m2。第二行为n个整数，从左到右依次为s[1],s[2]……s[n]
输入样例 1
3 0 0
1 1 1
输出样例 1
3 3

题目解答

假设，我们已经有一组数字，我们继续添加数字时：当前这组数字的max-min要么增大，要么不变。而删除数字时，要么变小，要么不变（想想为什么）。可以用双指针来完成这个搜索的操作。

算法具体实现时，我们只要让l从1循环到n，r不断的向右跑以满足要求就可以了。求一堆数的最小最大值，并可以进行插入删除操作。这一部分用任意一种二叉搜索树就可以完成，比如红黑树。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<set>

#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)

long n, m1, m2, num[100005], sum[100005];
long a, b;
multiset<long, less<long>> subarr;

int main(){
    cin >> n >> m1 >> m2;
    for(int i = 1; i <= n; i++) {
        cin >> num[i];
        sum[i] = num[i] + sum[i - 1];
    }

    subarr.insert(num[1]);
    int l = 1, r = 1; 
    while (l <= n && r <= n && l <= r) {
        long ans = *(--subarr.end()) - *subarr.begin();
        if (m1 <= ans && ans <= m2) {
            if (r - l + 1 > a) {
                a = r - l + 1;
                b = sum[r] - sum[l - 1];
            } else if (r - l + 1 == a) {
                b = MAX(b, sum[r] - sum[l - 1]);
            }
            subarr.insert(num[++r]);
        } else if (ans > m2) {
            subarr.erase(subarr.find(num[l++]));
        } else if (ans < m1) {
            subarr.insert(num[++r]);
        }
    }

    cout << a << ' ' << b << endl;
    return 0;
}

题目描述•其二

设B = {b1, b2, …, bn} 和 W = {w1, w2, …, wn}分别为平面上黑点和白点的两个集合。一黑点bi = (xi, yi) 与一白点wj = (xj, yj) 匹配当且仅当 xi <= xj 和 yi <= yj 同时成立，每个点最多只能用于一次匹配，请找出黑白点之间的最大匹配数目。

  • 黑点和白点各自的数量均不超过100000;
  • 平面为(0, 0)到(10000, 10000)的矩形中的整数点
  • 黑点白点坐标可能相同，B集合、W集合中也可能包含相同的元素

输入的第一行包括一个整数T (1 <= T <= 10)，表示有T组测试数据.
对于每组测试数据：
第一行两个整数，n(黑点个数) m(白点个数)，0 < n, m <= 100000
接下来n行每行有两个整数并用空格隔开：
黑点的横坐标x 黑点的纵坐标y
再接下来m行每行有两个整数同样用空格隔开：
白点的横坐标x 白点的纵坐标y

输出
对于每组测试数据，输出一行一个整数，表示最大匹配数。

样例

输入样例 1
2
2 2
1 0
0 1
1 1
0 0
1 1
1 1
0 0
输出样例 1
1
0

题目解答

思路上可能有点贪心的思想，假设问题是一维的，对所有黑点白点做离散化，然后从小到大扫描。因为白点总要大于等于黑点才可以匹配，所以每当我们扫描到一个白点时，将离他最近的黑点匹配到一起。

二维的情况就需要维护一个查找，这个查找每次能将Y轴最近的黑点与白点匹配。

离散化的时候注意x轴坐标相等就排序Y轴，x与y均相等，要把白点坐标排在后面。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<set>
#include<vector>
#include<algorithm>

struct Node {
    int x, y;
    bool black;
    inline bool operator () (const Node &a, const Node &b) {
        bool f = a.x < b.x;
        if (a.x == b.x) {
            f = a.y < b.y;
            if (a.y == b.y) {
                f = a.black;
            }
        }
        return f;
    }
};

int t;
int main(){
    cin >> t;
    while(t--) {
        int n, m, ans = 0;
        multiset<int, greater<int>> tree;
        cin >> n >> m;
        vector<Node> bw(n + m);
        for(int i = 0; i < n; i++) {
            Node d;
            cin >> d.x >> d.y;
            d.black = true;
            bw[i] = d;
        }
        for(int i = 0; i < m; i++) {
            Node d;
            cin >> d.x >> d.y;
            d.black = false;
            bw[n + i] = d;
        }

        sort(bw.begin(), bw.end(), Node());

        for (int i = 0; i < n + m;i++) {
            Node &d = bw[i];
            if (d.black) {
                tree.insert(d.y);
            } else {
                multiset<int>::iterator lower = tree.lower_bound(d.y);
                if(lower != tree.end() && *lower <= d.y) {
                    ans++;
                    tree.erase(lower);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}