题解 | #小O的糖果#

题目链接

题目描述

初始有三盒糖果，数量分别为 $a, b, c$ 。现在有 $k$ 颗新糖果，需要将它们全部分配到 $m$ 个新的空盒子中，且每个新盒子至少要放一颗糖果。

分配完成后，总共有 $3+m$ 盒糖果。问题是：是否存在一个盒子的编号是确定且唯一的，使得无论 $k$ 颗糖果如何分配，该盒子里的糖果数总是最多的？

解题思路

这是一道逻辑分析题。题目的核心在于“无论如何分配”，这意味着我们需要找到一个在所有可能情况下都满足条件的场景，而不是寻找某一种特定的分配方案。如果存在任何一种分配方案能够使得“唯一胜者”的地位被动摇（例如出现并列胜者，或胜者改变），那么答案就是 "NO"。

1. 谁有资格成为“必定”的唯一胜者？

新盒子？ 不可能。新盒子的糖果数是我们自己分配的，其数量是可变的。我们总可以通过调整分配方案（例如，将糖果均分）来避免任何一个新盒子成为唯一的胜者。因此，一个“必定”的胜者不可能来自新盒子。
初始盒子？ 这是唯一可能。初始三盒糖果的数量 $a, b, c$ 是固定的。如果其中一个的数量足够大，它就有可能在所有情况下都保持领先地位。

2. 成为“必定唯一胜者”的两个条件

假设某个初始盒子（不妨设是数量为 $a$ 的那个）是这个必定唯一的胜者，那么它必须同时满足以下两个条件：

条件一：在初始三者中，它必须是唯一的最大值。

如果初始时就有两个或三个盒子的糖果数并列最多（例如 $a=b \ge c$ ），那么至少已经有两个候选者了。只要我们把 $k$ 颗糖果分配给 $m$ 个新盒子，并确保每个新盒子的糖果数都小于 $a$ ，那么最终就会出现并列最多的情况（盒子 $a$ 和 $b$ ）。这样胜者就不是唯一的。因此，要成为必定胜者，其糖果数必须严格大于另外两个初始盒子。
条件二：它必须能胜过“最强”的新盒子。

要保证初始盒子在任何分配方案下都是胜者，它的糖果数就必须比一个新盒子可能达到的最大值还要多。一个新盒子能拥有的最多糖果数是多少？当我们想让一个新盒子糖果最多时，我们会给其他 $m-1$ 个新盒子各分配 1 颗（满足“至少一颗”的底线要求），然后把剩下的所有 $k - (m-1)$ 颗糖果都给这一个盒子。所以，一个新盒子能达到的最大糖果数是 $k - m + 1$ 。为了保证初始盒子必定唯一获胜，它的糖果数必须严格大于 $k - m + 1$ 。

结论

只有当上述两个条件同时满足时，才存在一个“确定且唯一”的最多糖果的盒子，答案为 "YES"。任何一个条件不满足，我们都能找到一种分配方案来打破这种唯一性，答案即为 "NO"。

算法流程:

找出 $a, b, c$ 中的最大值 max_val。
统计 max_val 在 $a, b, c$ 中出现的次数 count_max。
如果 count_max > 1，则不满足条件一，输出 "NO"。
如果 count_max == 1，则计算新盒子可能的最大糖果数 max_new = k - m + 1。
判断是否 max_val > max_new。如果是，则满足条件二，输出 "YES"；否则，输出 "NO"。

代码

cpp
java
python

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long a, b, c, k, m;
    cin >> a >> b >> c >> k >> m;

    long long max_val = max({a, b, c});
    int count_max = 0;
    if (a == max_val) count_max++;
    if (b == max_val) count_max++;
    if (c == max_val) count_max++;

    if (count_max > 1) {
        cout << "NO" << endl;
        return 0;
    }

    long long max_new = k - m + 1;

    if (max_val > max_new) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long k = sc.nextLong();
        long m = sc.nextLong();

        long max_val = Math.max(a, Math.max(b, c));
        int count_max = 0;
        if (a == max_val) count_max++;
        if (b == max_val) count_max++;
        if (c == max_val) count_max++;

        if (count_max > 1) {
            System.out.println("NO");
            return;
        }

        long max_new = k - m + 1;

        if (max_val > max_new) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

import sys

def solve():
    a, b, c = map(int, sys.stdin.readline().split())
    k, m = map(int, sys.stdin.readline().split())

    initial_candies = [a, b, c]
    max_val = max(initial_candies)
    
    count_max = initial_candies.count(max_val)

    if count_max > 1:
        print("NO")
        return

    # k candies into m boxes, each must have at least 1.
    # To maximize one box, give 1 to m-1 boxes.
    # The max value for a new box is k - (m - 1) * 1
    max_new = k - m + 1
    
    if max_val > max_new:
        print("YES")
    else:
        print("NO")

solve()

算法及复杂度

算法: 逻辑推理、贪心
时间复杂度: 整个过程只涉及几次比较和基本的算术运算，与输入规模无关，因此时间复杂度为 $\mathcal{O}(1)$ 。
空间复杂度: 只使用了常数个变量来存储输入和中间结果，空间复杂度为 $\mathcal{O}(1)$ 。