解题思路: 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语言代码)浏览:345 |
【偶数求和】 (C语言代码)浏览:670 |
WU-图形输出 (C++代码)浏览:823 |
WU-输出正反三角形 (C++代码)浏览:1069 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:749 |
良心推荐——>题解1049:C语言程序设计教程(第三版)课后习题11.1 (C语言描述——简单明了,时间复杂度低)浏览:1308 |
C语言训练-字符串正反连接 (C语言代码)浏览:650 |
明明的随机数 (C语言代码)浏览:963 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:727 |
判定字符位置 (C++代码)浏览:721 |