11285690 小O的糖果

链接: https://www.nowcoder.com/practice/c090ece039314d578e51913e758ce262

标签: 贪心, 基础数学

难度: 中等

---

题意

小O有三盒糖果，数量分别为 a、b、c。他新获得 n 颗糖果，要恰好分到 k 个新盒子中（每盒至少 1 颗）。最终共有 3+k 盒糖果。问：无论 n 颗糖果如何分配，糖果最多的那一盒编号是否确定且唯一？

---

分析

设原始三盒的最大值 M = max(a, b, c)，cnt_M 为原始三盒中等于 M 的盒子数。

核心观察

k 个新盒子分 n 颗糖（每盒 ≥ 1），新盒中单盒最大值的范围是：

• 下界（尽量均分）：ceil(n/k)
• 上界（一盒尽量多）：n - k + 1

分情况讨论

情况一：k = 1

只有一种分法：新盒固定得到 n 颗糖。只需检查 [a, b, c, n] 中最大值是否唯一：

• n > M：新盒（第4盒）唯一最大 → YES
• n == M：新盒与某原始盒并列 → NO
• n < M：原始盒中有唯一最大值（cnt_M == 1）→ YES，否则 → NO

情况二：k > 1

对于 k > 1，新盒的最大值可以通过不同分法变化，且不同分法可以让不同的新盒成为最大。所以：

• 新盒能赢的情况（ceil(n/k) > M）：新盒组总会赢过原始盒，但 k > 1 时可以调整分法让不同新盒成为最大，答案始终是 NO。
• 原始盒必赢的情况（n - k + 1 < M）：无论如何分配，新盒最大值上界 n-k+1 < M，原始最大盒一定赢。此时还需 cnt_M == 1（原始最大盒唯一）→ YES。
• 其他情况（存在某种分法让新盒赢、某种让原始盒赢，或原始最大不唯一）→ NO。

综合 k > 1 的条件：YES 当且仅当 n - k + 1 < M 且 cnt_M == 1。

---

复杂度

• 时间：O(1)
• 空间：O(1)

---

代码

C++

#include <bits/stdc++.h>
using namespace std;

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

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

    long long M = max({a, b, c});
    int cnt_M = (a == M) + (b == M) + (c == M);

    if (k == 1) {
        if (n > M) {
            cout << "YES" << endl;
        } else if (n == M) {
            cout << "NO" << endl;
        } else {
            cout << (cnt_M == 1 ? "YES" : "NO") << endl;
        }
    } else {
        if (n - k + 1 < M && cnt_M == 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

Java

import java.util.Scanner;

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

        long M = Math.max(a, Math.max(b, c));
        int cnt_M = (a == M ? 1 : 0) + (b == M ? 1 : 0) + (c == M ? 1 : 0);

        if (k == 1) {
            if (n > M) {
                System.out.println("YES");
            } else if (n == M) {
                System.out.println("NO");
            } else {
                System.out.println(cnt_M == 1 ? "YES" : "NO");
            }
        } else {
            if (n - k + 1 < M && cnt_M == 1) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

---

样例验证

样例1：a=4, b=2, c=3, n=2, k=2

M=4, cnt_M=1, k>1, n-k+1 = 1 < 4 → YES ✓

样例2：a=5, b=3, c=6, n=100, k=2

M=6, cnt_M=1, k>1, n-k+1 = 99 ≥ 6 → NO ✓