小球

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

比较每交换一对红蓝球带来的固定收益，决定是否交换到上限。

OJ: luogu

题目 ID: P2705

难度:入门

标签:数学贪心

日期: 2026-06-18 20:52

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 R 个红盒子、B 个蓝盒子，以及对应数量的红球和蓝球。 同色放置分别得 C、D 分，异色放置都得 E 分。 要求求出最大总得分。

思路

先看一个可以直接验证想法的朴素解：

可以枚举交换了多少对红蓝球，直接计算每种方案的得分。

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

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

    long long R, B, C, D, E;
    cin >> R >> B >> C >> D >> E;

    long long ans = LLONG_MIN;
    for (long long t = 0; t <= min(R, B); t++) {
        long long cur = (R - t) * C + (B - t) * D + 2 * t * E;
        ans = max(ans, cur);
    }

    cout << ans << '\n';
    return 0;
}

关键在于：每多交换 1 对红蓝球，得分变化始终是固定的：

text
2E - C - D

所以只要看这个值的正负：

  • 如果大于 0，就尽量多换；
  • 如果小于等于 0，就一个都不换。

代码

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

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

    long long R, B, C, D, E;
    cin >> R >> B >> C >> D >> E;

    long long ans = R * C + B * D;
    long long gain = 2 * E - C - D;
    if (gain > 0) {
        ans += 1LL * min(R, B) * gain;
    }

    cout << ans << '\n';
    return 0;
}

复杂度

主解只做常数次计算，时间复杂度 O(1)O(1)，空间复杂度 O(1)O(1)。

总结

这题的本质是一个“每次操作收益固定”的贪心判断。