对拍练习：线段覆盖问题

1
2
3
4
5

p1803-stress/
├── gen.cpp           # 随机数据生成器
├── wrong_greedy.cpp  # 待验证的贪心（故意写错）
├── brute.cpp         # 标准答案：01 序列
└── check.sh          # 自动对拍脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// gen.cpp —— 随机数据生成器
// 生成 n 个短区间(允许重复), 规模控制在 n <= 8, 方便暴力 DFS 对拍
#include <bits/stdc++.h>
using namespace std;

random_device rd;
mt19937 rng(rd());

int rnd(int l, int r) {
    return rng() % (r - l + 1) + l;
}

int main() {
    int n = rnd(4, 8);
    cout << n << '\n';

    for (int i = 0; i < n; i++) {
        int l = rnd(1, 15);
        int r = rnd(l + 1, 20);
        cout << l << ' ' << r << '\n';
    }
    return 0;
}

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

// wrong_greedy.cpp —— 故意写错的贪心: 按开始时间排序
// 直觉: 开始得越早越应该参加. 这个直觉是错的, 用对拍找反例.
#include <bits/stdc++.h>
using namespace std;

int n;
int L[100], R[100]; // L[i] / R[i]: 第 i 场比赛的开始 / 结束时间
int id[100];        // 排序用的下标数组

// 按开始时间升序
bool cmp_start(int x, int y) {
    if (L[x] != L[y]) return L[x] < L[y];
    return R[x] < R[y];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> L[i] >> R[i];
        id[i] = i;
    }

    // 错误策略: 开始时间最早的优先
    sort(id, id + n, cmp_start);

    int ans = 0;
    int last = INT_MIN;

    for (int i = 0; i < n; i++) {
        int k = id[i];
        if (L[k] >= last) {
            ans++;
            last = R[k];
        }
    }

    cout << ans << '\n';
    return 0;
}

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

// brute.cpp —— 标准答案: 01 序列
// b[i] = 0 表示不参加第 i 场, b[i] = 1 表示参加第 i 场
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20; // 对拍时 n <= 8

int n;
int ans = 0;
int L[maxn], R[maxn]; // 第 i 场比赛的开始 / 结束时间
int b[maxn];          // 01 序列

// 检查当前的 01 序列是否合法: 任意两场被选中的比赛都不能冲突
bool check() {
    for(int i = 1;i <= n ;++i ) {
        if( b[i] == 0) continue;
        for(int j = i+1;j <= n ;++j ) {
            if( b[j] == 0) continue;
            // 首尾相接不算冲突, 只有真正重叠才算
            if( L[i] < R[j] && L[j] < R[i]) return false;
        }
    }
    return true;
}

// dep: 现在决定第 dep 场比赛选不选
void dfs(int dep) {
    if( dep > n) {
        if( !check() ) return;
        int cnt = 0;
        for(int i = 1;i <= n ;++i ) // i: 数一数选了几场
            cnt += b[i];
        ans = max(ans,cnt);
        return;
    }
    for(int i = 0;i <= 1 ;++i ) // i: 0->1
    {
        b[dep] = i;
        dfs(dep+1);
    }
}

int main () {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
        std::cin >> L[i] >> R[i];
    dfs(1);
    std::cout << ans << "\n";
    return 0;
}

1
2
3
4

for(int i = 0;i <= 1 ;++i ) {
    b[dep] = i;
    dfs(dep+1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#!/bin/bash
# check.sh —— 对拍脚本
# ./wrong_greedy 是被测程序, ./brute 是标准答案(01 序列暴力)

g++ -o gen gen.cpp || exit 1
g++ -o wrong_greedy wrong_greedy.cpp || exit 1
g++ -o brute brute.cpp || exit 1

for i in {1..100}; do
	printf "\r$i"

	./gen >in                       # 生成数据
	./brute <in >out_std            # 标准答案
	./wrong_greedy <in >out_g       # 被测程序

	diff -b out_g out_std || exit 1
done

1
2

chmod +x check.sh
./check.sh

1
2
3
4
5

7
1c1
< 1
---
> 2

1
2
3

cat in        # 反例数据
cat out_g     # 贪心答案
cat out_std   # 暴力答案

1
2
3
4
5

4
1 10
2 3
4 5
6 7

1
2
3
4
5
6
7
8

// 正确策略: 结束时间最早的优先
bool cmp_end(int x, int y) {
    if (R[x] != R[y]) return R[x] < R[y];
    return L[x] < L[y];
}

// 主函数里改成:
sort(id, id + n, cmp_end);