题解 P7107 【天选之人】

## Solution 按照题面要求，在 $m$ 个人中恰好有 $p$ 个人抽到的带记号纸团数相同且最多。所以我们不妨小小贪心一下**直接让他们往多里拿，能拿多少拿多少** #### 正确性证明 ~~其实非常简单，你拿的多了那么剩下的人拿的就少了，你自然拿到的就更多~~ 我们不妨先假设他们每个人都拿了 $damedane$ 个带记号的纸团罢 ` int damedane; ` 那么 $damedane$ 需要满足什么条件呢？ 1. 你不能从四维空间里拿出带记号纸团来，所以所有 $p$ 个人一共只能拿不大于 $k$ 个带记号纸团：$damedane \times p <= k$ 2. 俗话讲不能吃不该吃的东西，所以每个人只能拿至多 $m$ 个纸团：$damedane <= m$ 所以最大值要怎么取呢？ $damedane = min (k \div p , m)$ 即 ` damedane = k / p > m ? m : k / p; ` 既然这 $p$ 个人每个人都拿了最多的纸团了，那么我们就开始验证罢。什么条件下这种情况就成立了呢？ 1. 剩下的在尽可能多的情况下每个人都比这 $p$ 个人拿的少对就一条。那么怎么让剩下的每个人都比这 $p$ 个人拿的少的情况下都拿尽可能多呢？我们不妨先假设他们每个人都拿了 $dameyo$ 个带记号的纸团罢 ` int dameyo; ` 怎么样最少？每个剩下的都拿 $(damedame - 1)$ 个，直到拿完为止。 #### 正确性证明 ~~其实更简单，你拿的少了同类兄弟要分摊的就多了，所以你要尽可能多拿~~ 然后我们就可以算 $dameyo$ 了对 $dameyo$ ，我们可以通过以下方式计算：对前 $\frac{(k - damedane \times p)}{damedane - 1}$ 个，每个人拿 $damedane - 1$ 个如果有多余的话，再来一个兜底剩下的不拿然后我们判断下所有 $n - p$ 个人拿完以后剩没剩下就可以了怎么判断呢？判断$\frac{(k - damedane \times p)}{damedane - 1}$ ( 可能 + 1 ) 个人有没有超过 $n - p$ 就可以了 ### 特判1 _" 如果有多余的话，再来一个兜底 "_ 其实这个多余的就是判断下 $\frac{(k - damedane \times p)}{damedane - 1}$ 有没有余数就可以了 _" 可能 + 1 "_ ### 特判2 一种情况是 $n = p$ ，所以如果按照上面的式子来算 $dameyo$ 的话就会很悲惨的 **$Segmention \ Fault$** (除数为0) 所以加个特判就好了 (这俩特判搞了我一个半小时) ## AC Code ( C Language ) ```cpp #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; } ```

<<< Return to archive list