HDU 3177 Crixalis's Equipment

http://acm.hdu.edu.cn/showproblem.php?pid=3177

/*
最初贪心想按bi降序排列--->>首先放入需求区间大的
-->>但是发现有很多反例。。例如

21 2
7 20
1 15 -->>先放bi = 20不可以但是先放bi = 15可以
正确贪心-->>假设放两件家居
ai bi
第一件家居 a1 b1
第二件家居 a2 b2
假设先放第一件家居 :
放第一件家居时满足的条件 V >= b1
放第二件家居时满足的条件 V >= a1+b2;

假设先放第二件家居 :
放第二件家居时满足的条件 V >= b2
放第一件家居时满足的条件 V >= a2+b1;

可以发现每一次放入家居时最大临时空间是a1+b2 和 a2+b1
那么贪心地取这两者之间较小的使得放入的可能性变大
ai在前表示ai先放入 --->>>取min(a1+b2, a2+b1)
即按照 a1+b2 < a2+b1 --->> b1 - a1 > b2 - a2排序即可

扩展到n件家居每次要求满足的条件都是剩余空间V‘ >= ai + bj//i是前一个放入的 j 是将要放入的
那么贪心策略便是使 ai+bj这个临时最大空间最小

数学模型-->>递推公式满足 V >= ∑(i =1 to n-1)ai + bn

贪心常见做法

1、可以推导归纳出函数或递推式的如本题再求最大求最小即可

2、有很多种选项但是搜索会爆掉那么尝试考虑交换两个选项的顺序会对结果改变什　

　　么最优的结果便是无论交换哪两个的顺序都不如原来的解优

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 typedef pair<int, int> P; //first -->>Ai
 8 
 9 P p[1024];
10 
11 bool cmp(P p1, P p2)
12 {
13     return (p1.second - p1.first) > (p2.second - p2.first);//bi - ai降序
14 }
15 
16 int main()
17 {
18     freopen("in.txt", "r", stdin);
19     int T, V, N;
20     scanf("%d", &T);
21    // printf("%d
",T);
22     while (T--)
23     {
24         getchar();
25         scanf("%d%d",&V, &N);
26         for (int i = 0; i < N; i++)
27         {
28             scanf("%d%d", &p[i].first, &p[i].second);
29         }
30         sort(p, p+N, cmp);
31         bool judge = true;
32         for (int i = 0; i < N; i++)
33         {
34             if (p[i].second <= V)
35             {
36                 V = V - p[i].first;
37             }
38             else
39             {
40                 judge = false;
41                 break;
42             }
43         }
44         if (judge) printf("Yes
");
45         else printf("No
");
46     }
47     return 0;
48 }