蓝桥杯算法提高VIP

算法提高VIP"/>

蓝桥杯算法提高VIP

题目

题目链接

题解

贪心。

类似于银行家算法？（逃

贪心思路：
通过常识可知，我们肯定让那些积木够数的小朋友先玩，玩完后把自己的全部积木交出来，作为空闲积木供其他小朋友使用；不够的小朋友中那些差积木数最少的先用，这样他用完之后又可以将他原来持有的积木贡献出来了，空闲积木就会变多了。

代码思路：
按每个小朋友的所需积木数与所有积木数的差值进行从小到大排序，通过一个变量存储空闲积木数，遍历每个小朋友，若空闲积木数加其已拥有的积木数满足所需的积木数，则这个小朋友可以完成，空闲积木数加上其已拥有的积木，继续遍历，直到最后都可以玩输出YES；若中途某个小朋友无法完成，则直接break，输出NO。

代码

#include<bits/stdc++.h>
using namespace std;struct peo{int have, all;
}p[10010];int n, T;bool cmp(peo a, peo b) {return a.all-a.have < b.all-b.have;
}int main()
{cin>>T;while(T--) {int flag = 0, sum = 0; //sum表示空闲积木数量cin>>n;for(int i = 1;i <= n;i ++) cin>>p[i].have>>p[i].all;sort(p+1, p+n+1, cmp);for(int i = 1;i <= n;i ++) {if(p[i].have + sum >= p[i].all) sum += p[i].have; else {puts("NO"); flag = 1; break;}}if(!flag) puts("YES");}return 0;
}