打卡信奥刷题（546）用C++信奥P7107[普及组/提高] 天选之人

rogeliu

3659人浏览 · 2025-01-05 12:16:44

rogeliu · 2025-01-05 12:16:44 发布

天选之人

题目背景

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

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

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

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

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

题目描述

好奇的 Gnar 想研究一般情况下抽到最多记号的人数。他给参与抓阄的 $n$ 人一人准备了 $m$ 张捏好的纸团，一共 $nm$ 张，其中恰好 $k$ 张提前写了记号。随后每个人在均匀打乱的纸团中各抽 $m$ 张。

一个人抽到最多的记号，当且仅当没有人抽到的记号比他还多。请你帮 Gnar 判断是否可能会恰好 $p\boldsymbol{p}$ 个人抽到最多的记号。Gnar 喜欢追根问底，所以如果有可能，你还需构造每个人抽的纸团中分别有多少带记号、有多少不带记号。

形式化地，假设第 $i$ 个人抽到了 $x_i$ 张带记号的纸团和 $y_i$ 张不带记号的纸团，你的构造应满足：

$xi,yi≥0x_i, y_i \ge 0$ ， $x_i + y_i = m$ 。
$∑i=1nxi=k\displaystyle \sum_{i = 1}^{n} x_i = k$ 。
有且仅有 $p\boldsymbol{p}$ 个互不相同的 $j$ 使 $xj=max⁡i=1n{xi}\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

3 3 5 2

样例输出 #1

样例 #2

样例输入 #2

3 3 3 2

样例输出 #2

NO

样例 #3

样例输入 #3

3 3 5 3

样例输出 #3

NO

提示

【样例解释 #1】

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

【样例解释 #2】

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

【数据规模与约定】

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

Subtask #1 (15 points)： $\le 8$ 。
Subtask #2 (15 points)： $\le 100$ 。
Subtask #3 (20 points)： $\le 10^5$ 。
Subtask #4 (10 points)： $p = 1$ 。
Subtask #5 (40 points)：无特殊限制。

对于所有的数据，保证 $\le p \le n \le {10}^5$ ， $\le m \le {10}^9$ ， $\le k \le n m$ 。

C++实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long long n, m, k, p, t, tot, tmp;
int main(){
scanf(“%lld%lld%lld%lld”, &n, &m, &k, &p);
tot = k;
t = k / p > m ? m : k / p;
tot -= t * p;
if (n == p){
if (t * p == k)
{
printf(“YES\n”);
for (int i = 1; i <= n; ++i)
printf(“%lld %lld\n”, t, m - t);
}
else
printf(“NO\n”);
}
else{

    if ((n - p) * (t - 1) < tot)
        printf("NO\n");
    else{
        printf("YES\n");
        for (int i = 1; i <= p; ++i)
            printf("%lld %lld\n", t, m - t);
        for (int i = p + 1; i <= n; ++i)
        {
            if (tot < (t - 1))
                printf("%lld %lld\n", tot, m - tot);
            else
                printf("%lld %lld\n", t - 1, m - t + 1);
            tot -= t - 1;
            if (tot < 0)
                tot = 0;
        }
    }
}
return 0;

}

在这里插入图片描述