python-盾神与积木游戏

解题思路:

假设用大小为n*2的数组stu存储学生，stu[i][0]表示第i个学生拥有的积木，stu[i][1]表示第i个学生需要的积木

这道题，如果能想到根据（stu[i][1]-stu[i][0]）的值从小到大对stu数组进行排序的话，就已经成功一大半了。

①准备工作，初始化stu数组，对stu数组进行排序，用idle存储可被借用的积木个数，用vis数组标记第i个学生是否能完成，0表示未完成，1表示已完成

②对学生数组进行遍历，如果stu[i][0]+idle >= stu[i][1]，则vis[i] = 1，idle = idle + stu[i][0]，否则，跳出循环。

③判断sum(vis) 是否等于n，如果是，输出YES，否则，输出NO。

注意事项:

参考代码:

def f(k):
    for it in range(k):
        n = int(input())
        stu = [[0,0] for i in range(n)]
        vis = [0 for i in range(n)]   #vis初始化全为0
        for i in range(n):   #记录stu数组
            stu[i][0],stu[i][1] = map(int,input().strip().split())
        stu = sorted(stu,key = lambda x:x[1]-x[0])   #关键一步，排序
        
        idle = 0   #初始化可被借用的积木数为0
        for i in range(n):
            if stu[i][0] + idle >= stu[i][1]:
                vis[i] = 1
                idle = idle + stu[i][0]
            else:    #如果idle不能满足积木差的少的同学的作品，那么更不可能完成后面积木差的多的同学的作品
                break
        if sum(vis) == n:
            print('YES')
        else:
            print('NO')

                    
if __name__ == '__main__':
    k = int(input().strip())
    f(k)