HDU ACM 3177 Crixalis's Equipment

Crixalis's Equipment

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2001 Accepted Submission(s): 805

【解题思路】这题只能说盛爷威武！盛爷给我们将贪心的时候将这题拿出来了，主要说说这题的思路，拿出两个装备，ai, bi, aj, bj, 假设两件装备都能放进去，那么先放置i后放置j至少需要的剩余空间是ai+bj；先放置j后放置i至少需要的剩余空间为bi+aj，那如果现在 ai+bj<bi+aj，那么得先放置i，后放置j，先不考虑这两者能不能真的放进去，但如果真的满足这样的不等式：ai+bj<bi+aj，那么就必须先考虑放i,因为其至少需要剩余空间的条件没有后者苛刻，i能放进去j可能放不进去，所以排序的话就找到了排序的理由

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define SIZE 1002
 5 
 6 using namespace std;
 7 
 8 typedef struct str{
 9     int first, second;
10 }Type;
11 
12 Type equip[SIZE];
13 
14 bool cmp(const Type& a, const Type& b)
15 {
16     return a.first+b.second<a.second+b.first;
17 }
18 
19 int main()
20 {
21     int T, size, n;
22     scanf("%d", &T);
23     while(T--)
24     {
25         scanf("%d%d", &size, &n);
26         for(int i=0; i<n; ++i)
27             scanf("%d%d", &equip[i].first, &equip[i].second);
28         sort(equip, equip+n, cmp);
29         bool flag = true;
30         for(int i=0; i<n; ++i)
31         {
32             if(equip[i].second <= size) size -= equip[i].first;
33             else
34             {
35                 flag = false;
36                 break;
37             }
38         }
39         if(flag) printf("Yes
");
40         else printf("No
");
41     }
42     return 0;
43 }