智力大冲浪：贪心算法求解游戏策略

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 m 元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为 n 个时段 (n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限 ti 前完成 (1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费 m 元中扣去一部分钱 wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱！

问题分析

我们用贪心算法来解决这个问题。贪心算法的思路是：每次都选择当前最优的选择，最终得到全局最优解。在本题中，我们需要选择游戏完成的顺序，使得最终的扣费最少。

贪心策略

**思路：**按照游戏的期限从小到大贪心，因为如果先做期限短的游戏，会占用后面做期限长的游戏的时间，导致很有可能后面的游戏没完成，扣除一大笔费用，因此需要优先完成期限短的游戏。对于期限相同的游戏，选择扣除更少的费用。

**做法：**将每个游戏的期限和扣费做成一个结构体，按照期限从小到大排序，然后从前往后贪心，记录当前已完成的游戏的最晚完成时间，如果可以在这个时间之前完成当前游戏，则完成，并更新最晚完成时间。如果无法在这个时间之前完成当前游戏，则不做这个游戏。

代码实现

def solve(m, n, t, w):
    # 将游戏信息存入列表
    games = [(t[i], w[i]) for i in range(n)]
    # 按照期限从小到大排序
    games.sort()
    # 初始化最晚完成时间
    last_time = 0
    # 初始化总收益
    total_money = m
    # 遍历游戏列表
    for game in games:
        # 如果当前游戏可以在最晚完成时间之前完成
        if game[0] > last_time:
            # 完成当前游戏
            total_money -= game[1]
            # 更新最晚完成时间
            last_time = game[0]
    # 返回最终的收益
    return total_money

# 输入数据
while True:
    m = int(input())
    n = int(input())
    t = list(map(int, input().split()))
    w = list(map(int, input().split()))
    # 输出结果
    print(solve(m, n, t, w))

测试用例

样例输入：

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

样例输出：

总结

本文介绍了如何使用贪心算法解决“智力大冲浪”节目中的游戏策略问题。贪心算法是一种简单有效的算法，它可以帮助我们找到问题的最优解。通过分析问题，找到贪心策略，并进行代码实现，我们可以轻松地解决这类问题。