C++贪心算法案例代码

题目描述

游戏中有n条龙，每条龙都有自身力量x及战胜它后的奖励力量 y，当你的力量超过龙时，才能打败龙和获得奖励力量。你可以自由选择挑战顺序，问最后你最多能打败多少条龙？

案例代码

这是一个经典的贪心算法问题。首先，你需要按照龙的力量从小到大进行排序。然后，你可以依次选择能够打败并获得奖励力量最多的龙来挑战。具体步骤如下：

1. 将所有的龙按照力量从小到大进行排序。
2. 从第一条龙开始，依次判断你的力量是否足以打败当前的龙，如果可以，就打败它并更新你的力量。
3. 继续向后判断下一条龙，重复步骤2，直到没有龙可以打败为止。

这个贪心算法的核心思想是每次选择当前能够打败并获得奖励力量最多的龙来挑战，从而保证最终能够打败尽可能多的龙。

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

struct Dragon {
    int strength;
    int reward;
};

bool compareDragons(const Dragon& d1, const Dragon& d2) {
    return d1.strength < d2.strength;
}

int maxDefeatedDragons(std::vector<Dragon>& dragons, int playerStrength) {
    std::sort(dragons.begin(), dragons.end(), compareDragons);

    int numDefeated = 0;
    for (const auto& dragon : dragons) {
        if (playerStrength > dragon.strength) {
            playerStrength += dragon.reward;
            numDefeated++;
        } else {
            break;  // 如果无法打败当前龙，则结束挑战
        }
    }

    return numDefeated;
}

int main() {
    std::vector<Dragon> dragons = {{10, 5}, {7, 8}, {3, 6}, {2, 4}};
    int playerStrength = 5;

    int result = maxDefeatedDragons(dragons, playerStrength);
    std::cout << "最多能打败的龙的数量：" << result << std::endl;

    return 0;
}

在这个案例代码中，我们首先定义了一个Dragon结构体来表示龙的属性，然后编写了一个compareDragons函数来帮助我们对龙进行排序。接着，maxDefeatedDragons函数实现了贪心算法的逻辑，并返回最多能打败的龙的数量。最后，在main函数中我们定义了一组龙和玩家的力量，然后调用maxDefeatedDragons函数得到结果并输出。