珍珠(bead)

形式化题目

有 $n$ 颗重量不同的珍珠（ $n$ 为奇数， $1 \le n \le 99$ ），现在给出 $m$ 对大小关系，每对关系形如“珍珠 $x$ 比珍珠 $y$ 重”。问：有多少颗珍珠绝对不可能是所有珍珠中重量排在最中间的（即第 $(n+1)/2$ 位）？

正解

思路

我们要找出绝对不可能排在正中间的珍珠。既然共有 $n$ 颗珍珠（ $n$ 是奇数），正中间的那颗珍珠恰好排在第 $(n+1)/2$ 位。这就意味着，对于正中间的那颗珍珠来说：

比它重的珍珠一定恰好有 $(n-1)/2$ 颗。
比它轻的珍珠也一定恰好有 $(n-1)/2$ 颗。

如果我们能确定某颗珍珠：

比它重的珍珠数量严格大于 $(n-1)/2$ 颗；
或者 比它轻的珍珠数量严格大于 $(n-1)/2$ 颗。只要满足上述其中一个条件，它就绝对不可能是最中间的珍珠。

题给的关系“ $x$ 比 $y$ 重”可以看作有向图中的一条有向边 $x \to y$ 。如果有向路径 $A \to \dots \to B$ 存在，那么根据传递性，珍珠 $A$ 必然比珍珠 $B$ 重。因此，可以使用 Floyd-Warshall 算法求出整个图的传递闭包。

设 g[i][j] 为 true 表示珍珠 $i$ 比珍珠 $j$ 重。求出传递闭包后：

g[i][j] = true 表示可以确定 $i$ 比 $j$ 重；
对每个 $i$ ，统计 g[i][j] 为 true 的个数（表示确定比 $i$ 轻的数量）；
对每个 $i$ ，统计 g[j][i] 为 true 的个数（表示确定比 $i$ 重的数量）。

如果两者中任意一个超过 $(n-1)/2$ ，这颗珍珠就是不可能处于中间位置的。累加这些珍珠的数量即为答案。

代码

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 16:15
# update_at: 2026-10-08 16:15

import sys

MAXN = 105          # 珍珠数上限 99，矩阵开到 105 留余量

# reach[i][j] 为 True 表示确定珍珠 i 比珍珠 j 重（含传递推出的关系）
type ReachMatrix = list[list[bool]]


def transitive_closure(reach: ReachMatrix, n: int) -> None:
    """原地求传递闭包：若 i 比 k 重且 k 比 j 重，则确定 i 比 j 重。"""
    for k in range(1, n + 1):
        row_k = reach[k]
        for i in range(1, n + 1):
            if reach[i][k]:
                reach[i] = [a or b for a, b in zip(reach[i], row_k)]


def count_not_middle(reach: ReachMatrix, n: int) -> int:
    """统计不可能是中位数的珍珠数：确定偏重或偏轻的数量超过 n/2 就不可能是中间那颗。"""
    half = n // 2  # n 为奇数，中位数必须恰好有 n/2 颗比它重的珍珠
    total = 0
    for i in range(1, n + 1):
        heavier = sum(reach[j][i] for j in range(1, n + 1))  # 确定比 i 重的珍珠数
        lighter = sum(reach[i][1 : n + 1])                   # 确定比 i 轻的珍珠数
        if heavier > half or lighter > half:
            total += 1
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    reach: ReachMatrix = [[False] * MAXN for _ in range(MAXN)]
    for _ in range(m):
        x, y = next(data), next(data)
        reach[x][y] = True

    transitive_closure(reach, n)
    print(count_not_middle(reach, n))


if __name__ == "__main__":
    solve()

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 16:15
 * update_at: 2026-10-08 16:15
 */
// ROJ 1384 珍珠(bead)：Floyd-Warshall 求传递闭包，统计有多少颗珍珠不可能是中位数。
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 105;
bool reach[MAXN][MAXN]; // reach[i][j] = true 表示确定珍珠 i 比珍珠 j 重（含传递推出的关系）

void solve() {
    ll n, m;
    if (!(cin >> n >> m)) return;

    for (ll k = 0; k < m; ++k) {
        ll x, y;
        cin >> x >> y;
        reach[x][y] = true; // 直接给出的关系：x 比 y 重
    }

    // 传递闭包：若 i 比 k 重且 k 比 j 重，则 i 比 j 重
    for (ll k = 1; k <= n; ++k)
        for (ll i = 1; i <= n; ++i)
            for (ll j = 1; j <= n; ++j)
                if (reach[i][k] && reach[k][j]) reach[i][j] = true;

    ll half = n / 2; // n 为奇数，中位数必须恰好有 n/2 颗比它重的珍珠
    ll not_middle = 0;
    for (ll i = 1; i <= n; ++i) {
        ll heavier = 0; // 确定比珍珠 i 重的珍珠数
        ll lighter = 0; // 确定比珍珠 i 轻的珍珠数
        for (ll j = 1; j <= n; ++j) {
            if (reach[j][i]) heavier++;
            if (reach[i][j]) lighter++;
        }
        if (heavier > half || lighter > half) not_middle++;
    }
    cout << not_middle << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

时间复杂度：计算传递闭包的 Floyd-Warshall 算法的时间复杂度为 $O(n^3)$ 。由于 $n \le 99$ ，计算量约在 $10^6$ 量级，完全可以在规定时间内运行完毕。最后统计每个节点信息需要 $O(n^2)$ 。总时间复杂度为 $O(n^3)$ 。
空间复杂度：需要一个 $O(n^2)$ 的邻接矩阵来存储有向图。对于 $n \le 99$ ，空间消耗极小。总空间复杂度为 $O(n^2)$ 。

总结

这是一道经典的偏序关系传递闭包应用题。

注意理解题意，所谓“绝对不可能是中间重量”，其等价于能明确判断出偏大或者偏小的数量超过一半。
图可能会不连通或者包含多条分支，通过传递闭包可以将所有隐含的确定关系推导出来。

目录

形式化题目

正解

思路

代码

复杂度

总结