解题思路:
先去掉手里的积木足够的小盆友,然后再从小到大排序、再加贪心。时间复杂度为O(m*n)在python中会超时。水平差、不知道如何去优化了,求大佬指教。
参考代码:
m = int(input()) for _ in range(m): n = int(input()) s = 0 #可以用的积木数量 L = [] #存手里积木数不足的小盆友 for _ in range(n): a,b = map(int,input().split()) if a >= b: s += a else: L.append([a,b]) L = sorted(L,key= lambda L:L[1]) #sorted排序,根据需要的积木数从小到大排序 for l in L: if l[0]+s >= l[1]: s += l[0] else: #剪枝,但没什么卵用 break if s >= L[-1][1]: #结束后判断能用的积木能不能满足需要积木最大的小盆友,能说明可以实现 print("YES") else: #否则不能实现 print("NO")
0.0分
0 人评分
C语言训练-求函数值 (C语言代码)浏览:944 |
C语言训练-排序问题<2> (C++代码)(sort函数)浏览:1720 |
大神老白 (C语言代码)浏览:768 |
C二级辅导-同因查找 (C语言代码)浏览:626 |
C二级辅导-进制转换 (C语言代码)浏览:657 |
计算质因子 (C++代码)浏览:1825 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:793 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:732 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:512 |
DNA (C语言描述,数据结构)浏览:909 |