解题思路: n个时段n个游戏,每个时段只能玩一个游戏,所以只需要给玩的游戏排个次序使总罚款最小。贪心点:按时段依次选择ddl(截止时间)最前的先玩,不着急的后玩,如果ddl相同则wi罚款多的先玩罚款少的后玩;如果该游戏已经过了ddl那肯定是要罚款的,但我们可以在done(已经完成且没有罚款的游戏的wi值
)找一下,看看能不能极限一换一找个最小的罚款;已经罚款的游戏可以直接舍弃排在最后玩,相当于不占用当前时段
注意事项:
参考代码:
Money = int(input()) N = int(input()) ddl = [int(i) for i in input().split()] wi = [int(i) for i in input().split()] list = [(ddl[i],wi[i]) for i in range(N)] list = sorted(list, key = lambda t:(t[0],-t[1])) done = [] # 已经完成且没有罚款的游戏的wi值 i = 0 # i指时段 while 1: i += 1 if len(list) == 0: break if list[0][0] >= i: # 未超时,不用罚款 done.append(list[0][1]) list.pop(0) else: # 已超时,要罚款 if list[0][1] > min(done): done.append(list[0][1]) list.pop(0) Money -= min(done) done.remove(min(done)) else: Money -= list[0][1] list.pop(0) i -= 1 # 已经罚款的游戏可以直接舍弃排在最后玩,相当于不占用当前时段 print(Money if Money>0 else 0)
0.0分
1 人评分
C语言训练-求1+2!+3!+...+N!的和 (C++代码)浏览:1172 |
母牛的故事 (C语言代码)浏览:739 |
模拟计算器 (C语言代码)浏览:886 |
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:613 |
不容易系列2 (C语言代码)浏览:593 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1307 |
用筛法求之N内的素数。 (C语言代码)浏览:1239 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1156 |
众数问题 (C语言代码)浏览:830 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:522 |