C++:赢奖金-（C++）

Question

C公司今年大盈利，老板很高兴，奖励每个员工者m元。但老板又有点小心眼，他不想 让你那么痛快的掌到奖励，他举办了一场比赛，所有员工参加完比赛之后才决定你能拿多少 奖金！ 接下来老板宣布比赛规侧： 比赛时间分为n个时段(n<=500)，比赛又给出了很多小游戏，每个小游戏都必须在规定期限ti时间段内完成。如果一个游戏没能在规定时间段内完成，则要从奖励费m元中扣取一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在1个时段内完成，而且都必须从整时段开始。老板只是想考一考每个参赛者如何安排组织自己做游戏的顺序。作为一个非常努力上进的员工，小明很想赢得冠军，当然更想赢取最多的钱！那么他改怎么选择才能赢得最多的钱！注意：比赛绝对不会让参赛者赔钱。 【输入格式】 第一行为m，表示奖励的钱。 第二行为n，表示有n个小游戏。 第三行有n个数，分别表示游戏1到n的规定完成期限时间段ti。 第四行有个数，分别表示游戏1到n不能在规定期限时间段内完成的扣款数额wi。 【输出格式】 输出一行，表示小明能赢取最多的钱 【样例输入】 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 【样例输出】 9950 数据说明 对于100%的数据，1≤n≤500，1≤m≤5×10^5，1≤ti≤n，1≤wi≤1000。

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

这个问题可以通过贪心算法来解决。贪心算法在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的。在这个场景中，贪心算法将选择扣款数额最大的游戏先完成，因为这样可以在有限的时间段内减少未按时完成游戏的罚款。

以下是解决这个问题的C++代码示例：

#include <iostream>
#include <vector>
#include <algorithm> // 用于std::sort

using namespace std;

// 定义一个结构体来存储游戏的时间段和扣款数额
struct Game {
    int ti;
    int wi;
};

int main() {
    int m, n;
    cin >> m >> n;

    // 读取每个游戏的时间段和扣款数额
    vector<Game> games(n);
    for (int i = 0; i < n; ++i) {
        cin >> games[i].ti;
    }
    for (int i = 0; i < n; ++i) {
        cin >> games[i].wi;
    }

    // 根据扣款数额降序排序游戏
    sort(games.begin(), games.end(), [](const Game &a, const Game &b) {
        return a.wi > b.wi;
    });

    // 遍历排序后的游戏，安排完成时间
    int time = 1; // 当前时间段
    for (const auto &game : games) {
        if (time <= game.ti) {
            // 如果当前时间段小于等于游戏的截止时间，则安排在当前时间段完成
            m -= game.wi; // 扣除罚款
            time++; // 进入下一个时间段
        } else {
            // 如果当前时间段已经超过了游戏的截止时间，则不扣款
            // 因为题目保证每个游戏都能在1个时间段内完成
        }
    }

    // 输出小明能赢取的最多奖金
    cout << m << endl;

    return 0;
}

这段代码首先定义了一个结构体Game来存储每个游戏的时间段和扣款数额。然后，它读取输入数据，并使用std::sort函数根据扣款数额对游戏进行降序排序。接着，它遍历排序后的游戏列表，根据当前时间段和游戏的截止时间来决定是否需要扣除罚款。最后，它输出小明在最佳策略下能赢取的最多奖金。

请注意，这段代码假设所有游戏都可以在1个时间段内完成，并且小明会尽可能地在每个时间段内完成游戏以避免罚款。如果有任何特殊情况或边界条件需要考虑，代码可能需要相应的调整。