解题思路:
先去掉手里的积木足够的小盆友,然后再从小到大排序、再加贪心。时间复杂度为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++代码)(预生成结果以节省每次生成的时间)浏览:808 |
C二级辅导-分段函数 (C语言代码)浏览:842 |
母牛的故事 (C语言代码)浏览:1715 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:600 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:978 |
printf基础练习2 (C语言代码)浏览:305 |
【金明的预算方案】 (C++代码)浏览:837 |
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:672 |
关于float,double变量的几点说明浏览:1810 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:498 |