蓝桥杯 盾神与积木游戏 贪心

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct Student{
 4     int h; //have,表示这个学生现在手里有的积木个数 
 5     int n; //need，表示这个学生所需要的积木总个数 
 6     int t;    //表示这个学生还需要的积木个数，也就是need-have 
 7 } s[10010]; //student结构体数组 
 8 bool cmp(Student s1, Student s2) {
 9     return s1.t < s2.t;
10 }
11 const int INF = 0x3f3f3f3f;
12 int main() {
13     int m;
14     cin >> m;
15     while (m--) {
16         int n;
17         cin >> n;
18         int sum = 0; //现在可以拿来分配的积木数 
19         int has = 0; //已经完成的人数 
20         for (int i = 1; i <= n; i++) {
21             cin >> s[i].h >> s[i].n;
22             if (s[i].h >= s[i].n) { //如果这个学生可以拼出积木 
23                 sum += s[i].h; //把他的积木充公，用来分给其他人 
24                 s[i].t = INF; //他不再需要积木了 
25                 has++; //已经完成的人数加1 
26             } else { //拼不成的话 
27                 s[i].t = s[i].n - s[i].h; //计算出他还需要的    
28             }
29         }
30         if (has == n) { //如果所有人完成了 
31             cout << "YES" << endl;
32             continue; 
33         }
34         sort(s + 1, s + 1 + n, cmp); 
35         bool flag = true;
36         for (int i = 1; i <= n - has; i++) { //遍历剩下的未完成的学生 
37             if (sum >= s[i].t) { //如果可用资源能满足这个学生的需求 
38                 sum += s[i].h; //充公 
39             } else  { //否则，死锁，都在等可用资源  
40                 cout << "NO" << endl;
41                 flag = false;
42                 break;
43             }
44         }
45         if (flag) {
46             cout << "YES" << endl;    
47         }
48     }
49     return 0;
50 }