lijyya's Blog
0%

一个有序对选择的模型

发表于 更新于 分类于 ， ， ， ，

问题概述

有 n 个有序对 \{a_i, b_i\} ，对于每个有序对，可以选择将 a_i 加入集合 A 或将 b_i 加入集合 B ，试最小化 max(A) + max(B) 。（规定 max(\varnothing)=0 ）

算法

对于 \{a_i, b_i\} 和 \{a_j, b_j\} ，如果满足 a_i \leqq a_j && b_i \leqq b_j ，就可以把他们两个合并在 \{a_j, b_j\} 上， \{a_i, b_i\} 可以直接舍弃。

处理方法：

对于一组乱序的有序对：

\{2, 3\}

\{1, 4\}

\{3, 1\}

\{4, 2\}

\{2, 7\}

\{1, 8\}

将有序对以 a_i 为第一关键字， b_i 为第二关键字从小到大排序，变成这个样子：

\{1, 4\}

\{1, 8\}

\{2, 3\}

\{2, 7\}

\{3, 1\}

\{4, 2\}

显然由贪心可以知道， b_i 应该单调递减，并且很容易知道最后一个有序对一定要保留。因此只需要从后往前遍历，舍弃掉破坏 b_i 单调性的有序对（等效于把无需舍弃的有序对加入新的数组，省时），变成这个样子：

\{4, 2\}

\{2, 7\}

\{1, 8\}

由贪心可以知道，如果选择了 a_i ，那么就可以无代价地选择之后的所有 a_i ，此时只需要选择上一个 b_i ，就组成目前最优解。（ b_i 相反）

相当于，比较每一个这种组合，不断更新得到最终答案：

\{N, Y\}

\{Y, N\}

( Y 代表选择， N 代表舍弃)

需要注意的是，若选择第一个 a_i 或选择最后一个 b_i ，就无需再加上另一边的值（都选择这一边的一定最优）。

例题 1

Grakn Forces 2020 D. Searchlights

题目大意

n 个强盗分别位于坐标 (a_i, b_i) ， m 个探照灯分别位于坐标 (c_i, d_i) 。

每次操作可以让每个海盗右移一格（ a_i++ ）或者上移一格（ b_i++ ）。

当且仅当 a_i \leqq c_j && b_i \leqq d_j 时探照灯可以照到海盗，若没有探照灯可以看到海盗，则说明海盗是安全的。

求使海盗安全的最少操作次数。

题解

可以求得每个海盗向上躲过探照灯需走 u_i 格，向右需要 v_i 格，把它变成一个有序对 (u_i, v_i) ，就转换成本模型。

代码实现

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
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e3 + 5;
 
int n, m;
 
struct Node{
    int a, b;
} rob[MAXN], sc[MAXN], tmp[MAXN * MAXN], tmp2[MAXN * MAXN];
int cnt, cnt2;
inline bool cmp(Node &x, Node &y) {
    if (x.a == y.a)
        return x.b > y.b; // 排序函数必须严格偏序，否则会出现未知错误
    return x.a > y.a;
}

set<pair<int, int> > s;
 
int main() {
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &rob[i].a, &rob[i].b);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &sc[i].a, &sc[i].b);
        if (s.count(make_pair(sc[i].a, sc[i].b))) {
            continue;
        }
        s.insert(make_pair(sc[i].a, sc[i].b));
        for (int j = 1; j <= n; ++j) {
            if (sc[i].a >= rob[j].a && sc[i].b >= rob[j].b) {
                tmp[++cnt].a = sc[i].a - rob[j].a + 1;
                tmp[cnt].b = sc[i].b - rob[j].b + 1;
            }
        }
    }
 
    if (!cnt) {
        puts("0");
        return 0;
    }
 
    sort(tmp + 1, tmp + 1 + cnt, cmp);
    tmp2[++cnt2] = tmp[1];
 
    int cur = 1;
    for (int i = 2; i <= cnt; ++i) {
        if (tmp[i].b > tmp2[cur].b) {
            ++cur;
            tmp2[++cnt2] = tmp[i];
        }
    }

    // int ans = tmp2[1].a + tmp2[cnt2].b;
    int ans = min(tmp2[1].a, tmp2[cnt2].b);
    for (int i = 1; i < cnt2; ++i) {
        ans = min(ans, tmp2[i].b + tmp2[i + 1].a);
    }
 
    printf("%d\n", ans);
}

例题 2

Codeforces Round #679 C. Perform Easily

题目大意

给定一个序列 a_1,a_2,...,a_6 ，分别对应吉他上的第 i 根琴弦，每根琴弦的品从 1 开始标号，弹奏 i 弦 j 品可以得到 a_i+j 的音符。

现想得到一个 n 个音符的旋律 b_1,b_2,...,b_n ，并且想让它弹奏最容易。弹奏的品的最大序号与最小序号越小，弹奏越容易。

求出可能的最小值。

题解

可以得到 n 个 6 元组，组内元素为 v[i][j]=b_i - a_j （ i \in [1,n] j \in [1,6] ），每组选择一个数，让选择的数的极差最小。

可以选择其中一个六元组固定下来（例如可以固定 v[1][] ），对于这组的每一个 v[1][k] ，都把其余各组中最大的 \geqq v[i][j] 的数和最小的 \leqq v[i][j] 的数找出来，分别求它们与 v[1][k] 的差（正数）（若没有满足某个条件的数，记对应的差为 inf ）。得到的就是第一个音符选择第 k 根弦，剩下的音符与其的品的差值。然后就转换成这个模型。这样我们算出了选固定组每一根弦时的最小极差，对六根弦的情况取一个最小值即可。

代码实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;

int a[7], b[MAXN];
int c[MAXN][7];

int main() {
    for (int i = 1; i <= 6; ++i) {
        scanf("%d", &a[i]);
    }

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 6; ++j) {
            c[i][j] = b[i] - a[j];
        }
    }
    
    if (n == 1) {
        puts("0");
        return 0;
    }

    int ans = INF;

    for (int k = 1; k <= 6; ++k) {
        vector<pair<int, int> > v;

        for (int i = 2; i <= n; ++i) {
            int l = INF, r = INF;
            for (int j = 1; j <= 6; ++j) {
                if (c[i][j] >= c[1][k]) {
                    r = min(r, c[i][j] - c[1][k]);
                }
                if (c[i][j] <= c[1][k]) {
                    l = min(l, c[1][k] - c[i][j]);
                }
            }

            v.push_back(make_pair(l, r));
        }

        if (v.empty()) {
            puts("0");
            return 0;
        }

        sort(v.begin(), v.end());

        vector<pair<int, int> > u;
        u.push_back(v[v.size() - 1]);

        for (int i = (int)v.size() - 2; i >= 0; --i) { // v.size() 是无符号
            if (v[i].second > u[u.size() - 1].second) {
                u.push_back(v[i]);
            }
        }

        int tmp = min(u[0].first, u[u.size() - 1].second);
        for (int i = 0; i <= (int)u.size() - 2; ++i) {
            tmp = min(tmp, u[i].second + u[i + 1].first);
        }

        ans = min(ans, tmp);
    }

    printf("%d\n", ans);
    return 0;
}