天选之人

GitHub 跳转原题关系图返回列表

设恰好 p 个人抽到最大记号数 t，则总记号数必须落在 [p t, p t + (n-p)(t-1)]，找到合法 t 后再贪心构造。

OJ: luogu

题目 ID: P7107

难度:普及+/提高

标签:数学构造思维

日期: 2026-06-20 06:15

题意

要把 k 张有记号的纸团分给 n 个人，每个人正好拿 m 张。

如果第 i 个人拿到的有记号纸团数是 x_i，那么要满足：

0 <= x_i <= m
x_1 + x_2 + ... + x_n = k
恰好有 p 个人的 x_i 等于全体最大值

如果能构造，就输出任意一组 x_i 和 m - x_i。

思路

先看一个直接验证小数据的暴力：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 n, m, k, p;
i64 x[25];
bool found = false;

void print_answer() {
    cout << "YES\n";
    for (int i = 1; i <= n; i++) {
        cout << x[i] << ' ' << (m - x[i]) << '\n';
    }
}

void dfs(int pos, i64 left) {
    if (found) {
        return;
    }

    if (pos == n + 1) {
        if (left != 0) {
            return;
        }

        i64 mx = -1;
        for (int i = 1; i <= n; i++) {
            mx = max(mx, x[i]);
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (x[i] == mx) {
                cnt++;
            }
        }

        if (cnt == p) {
            found = true;
            print_answer();
        }
        return;
    }

    for (i64 take = 0; take <= m && take <= left; take++) {
        x[pos] = take;
        dfs(pos + 1, left - take);
        if (found) {
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k >> p;
    dfs(1, k);

    if (!found) {
        cout << "NO\n";
    }

    return 0;
}

暴力版就是直接 DFS 枚举每个人拿到多少张有记号纸团，最后检查有没有恰好 p 个人并列最大。
它只能跑很小的数据，但很适合拿来对拍。

固定最大值 `t`

设最后恰好有 p 个人抽到了最大值 t。

那么这 p 个人一共贡献了：

p * t

其余 n - p 个人既然不是最大值，就最多只能拿到 t - 1 张记号。
因此总记号数 k 必须满足：

p * t <= k <= p * t + (n - p) * (t - 1)

这就是整题最关键的不等式。

反过来，如果我们找到了某个 t 满足这个区间，那就一定能构造：

先让前 p 个人都拿 t 张记号
剩下的 k - p * t 张记号，往后面 n - p 个人里塞
每个人最多塞到 t - 1 为止

这样做完之后：

前 p 个人都等于 t
其他人都严格小于 t
总和又正好是 k

所以条件也是充分的。

怎么直接判断有没有这样的 `t`

从不等式直接整理：

p * t <= k，得到 t <= floor(k / p)
k <= p * t + (n - p) * (t - 1) = n * t - n + p

第二条继续化简得到：

t >= ceil((k + n - p) / n)

所以只要看这个区间里有没有整数 t 即可：

ceil((k + n - p) / n) <= t <= min(m, floor(k / p))

再注意几个特判：

p = 0 一定无解
k = 0 时，只有所有人都拿 0 张记号，也就是 p = n 才有解
p = n 时，所有人都必须一样，所以需要 k % n = 0

代码

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
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
78
79
80
81
82
83
84
85
86
87
88
89
90#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 n, m, k, p;
i64 x[100005];

i64 ceil_div(i64 a, i64 b) {
    return (a + b - 1) / b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k >> p;

    if (p == 0) {
        cout << "NO\n";
        return 0;
    }

    if (k == 0) {
        if (p != n) {
            cout << "NO\n";
            return 0;
        }

        cout << "YES\n";
        for (int i = 1; i <= n; i++) {
            cout << 0 << ' ' << m << '\n';
        }
        return 0;
    }

    if (p == n) {
        if (k % n != 0) {
            cout << "NO\n";
            return 0;
        }

        i64 same = k / n;
        if (same > m) {
            cout << "NO\n";
            return 0;
        }

        cout << "YES\n";
        for (int i = 1; i <= n; i++) {
            cout << same << ' ' << (m - same) << '\n';
        }
        return 0;
    }

    // 设恰好 p 个人都抽到最大值 t。
    // 那么：
    // 1) 至少要有 p * t 张记号；
    // 2) 其余 n - p 个人每人至多 t - 1 张记号。
    i64 left = max<i64>(1, ceil_div(k + n - p, n));
    i64 right = min<i64>(m, k / p);

    if (left > right) {
        cout << "NO\n";
        return 0;
    }

    i64 t = left;
    i64 rest = k - p * t;

    for (int i = 1; i <= n; i++) {
        x[i] = 0;
    }
    for (int i = 1; i <= p; i++) {
        x[i] = t;
    }

    for (int i = p + 1; i <= n; i++) {
        i64 give = min(rest, t - 1);
        x[i] = give;
        rest -= give;
    }

    cout << "YES\n";
    for (int i = 1; i <= n; i++) {
        cout << x[i] << ' ' << (m - x[i]) << '\n';
    }

    return 0;
}

复杂度

主程序只做常数次计算和一次线性构造：

时间复杂度 $O(n)$
空间复杂度 $O(n)$

总结

这题表面是构造，核心其实是先把“恰好 p 个人并列最大”翻译成一个区间条件。

一旦固定最大值 t，问题就只剩两件事：

判断总和 k 能不能落进合法区间
如果能，就把剩下的记号数贪心塞给非赢家

思路非常短，但条件一定要写完整。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7107 天选之人

题目背景

暑假期间，学校不提供午餐，Gnar 只好找伙计们一起点外卖。

尴尬的是，外卖很快送到却没人乐意去校门口拿，毕竟户外可是 $35\degree\!\text{C}$ 高温！此时 Gnar 想到了好主意：“我给一人捏了一张纸团，其中一张写有记号，不如我们抓阄决定，谁抽到带记号的谁去拿！”

于是 Gnar 连续拿了六天的外卖。

这可让他不服又委屈：“换个规则！一人准备三张纸团，五张有记号，每人抽三张，记号最多的去拿！”

Gnar 紧张地展开手中的纸团，两个记号赫然映在眼前。大伙们刚想放声大笑他的非酋运气，有人缓缓举起三张纸片说道：“我也抽到了两个记号……”

题目描述

好奇的 Gnar 想研究一般情况下抽到最多记号的人数。他给参与抓阄的 $n$ 人一人准备了 $m$ 张捏好的纸团，一共 $nm$ 张，其中恰好 $k$ 张提前写了记号。随后每个人在均匀打乱的纸团中各抽 $m$ 张。一个人抽到最多的记号，当且仅当没有人抽到的记号比他还多。请你帮 Gnar 判断是否可能会恰好 $\boldsymbol{p}$ 个人抽到最多的记号。Gnar 喜欢追根问底，所以如果有可能，你还需构造每个人抽的纸团中分别有多少带记号、有多少不带记号。形式化地，假设第 $i$ 个人抽到了 $x_i$ 张带记号的纸团和 $y_i$ 张不带记号的纸团，你的构造应满足：

$x_i, y_i \ge 0$ ， $x_i + y_i = m$ 。
$\displaystyle \sum_{i = 1}^{n} x_i = k$ 。
有且仅有 $\boldsymbol{p}$ 个互不相同的 $j$ 使 $\displaystyle x_j = \max_{i = 1}^{n} \{x_i\}$ 。

输入格式

输入四个整数 $n, m, k, p$ ，含义详见题目描述。

输出格式

第一行输出 YES 或 NO（不区分大小写，yEs / No 均可），表示是否会恰好 $p$ 个人抽到最多的记号。如果第一行输出 YES，接下来 $n$ 行每行输出 $x_i, y_i$ ，表示每个人抽到带与不带记号的纸团个数。因答案可能不唯一，本题采用 Special Judge，只要构造符合题面中的要求均视为正确。

输入输出样例 #1

输入 #1

text

13 3 5 2

输出 #1

text

输入输出样例 #2

输入 #2

text

13 3 3 2

输出 #2

text

1NO

输入输出样例 #3

输入 #3

text

13 3 5 3

输出 #3

text

1NO

说明/提示

【样例解释 #1】

样例给出了一种满足题述条件的构造。

【样例解释 #2】

不论如何，记号的分布从高到低只有三种情况： $\{3,0,0\}$ ， $\{2,1,0\}$ ， $\{1,1,1\}$ ，抽到最多记号的人数分别对应 $1$ ， $1$ ， $3$ 。因此无法构造 $p = 2$ 的方案。

【数据规模与约定】

本题采用捆绑测试。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

Subtask #1 (15 points)： $n,m \le 8$ 。
Subtask #2 (15 points)： $n,m \le 100$ 。
Subtask #3 (20 points)： $n,m \le 10^5$ 。
Subtask #4 (10 points)： $p = 1$ 。
Subtask #5 (40 points)：无特殊限制。对于所有的数据，保证 $0 \le p \le n \le {10}^5$ ， $1 \le n$ ， $1 \le m \le {10}^9$ ， $0 \le k \le n m$ 。

天选之人

目录

题意

思路

固定最大值 t

怎么直接判断有没有这样的 t

代码

复杂度

总结

一图流解析

固定最大值 `t`

怎么直接判断有没有这样的 `t`