HDU 3177 Crixalis's Equipment（贪婪）「建议收藏」

主题链接：http://acm.hdu.edu.cn/showproblem.php?

pid=3177

Crixalis – Sand King used to be a giant scorpion(蝎子) in the deserts of Kalimdor. Though he’s a guardian of Lich King now, he keeps the living habit of a scorpion like living underground and digging holes.

Someday Crixalis decides to move to another nice place and build a new house for himself (Actually it’s just a new hole). As he collected a lot of equipment, he needs to dig a hole beside his new house to store them. This hole has a volume of V units, and Crixalis has N equipment, each of them needs Ai units of space. When dragging his equipment into the hole, Crixalis finds that he needs more space to ensure everything is placed well. Actually, the ith equipment needs Bi units of space during the moving. More precisely Crixalis can not move equipment into the hole unless there are Bi units of space left. After it moved in, the volume of the hole will decrease by Ai. Crixalis wonders if he can move all his equipment into the new hole and he turns to you for help.

      
        220 310 203 101 710 21 102 11      

   
   

    
    Yes
No
   
   

题意：

向一个容量为V的洞中放如入物品，每件物品有一个停放体积和一个可移动体积。问是否能放下全部的物品？

思路：—— 贪心

                                   停放体积         移动体积

                  第一件物品          a1             b1

                  第二件物品          a2             b2

如果这两件物品的移动体积都不大于洞的体积V

那么将单独比較两个物品的时候会发现：  a1+b2为先放第一件物品，后放第二件物品的最大瞬时体积

                                                        a2+b1为先放第二件物品。后放第一件物品的最大瞬时体积

那么我们就应该选择a1+b2和a2+b1中比較小的先放。

那么从2件物品。扩展到n件物品 如果n件物品的移动体积都不大于洞的体积V，

将N件物品依照a1+b2 < a2+b1进行排序，（事实上就是依照差值的大小）然后依次放入洞中。

PS: 

假设仅仅是单纯的依照Bi从大到小排序的话为WA；

看看这个案例就明确了。

21 2

8 18

1 20

Yes

代码例如以下：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
struct num
{
    int a, b;
} p[1017];
bool cmp(num A, num B)
{
    return A.b-A.a > B.b-B.a;
}
int main()
{
    int t;
    int v, n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&v,&n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d %d",&p[i].a,&p[i].b);
        }
        sort(p,p+n,cmp);
        int i;
        for(i = 0; i < n; i++)
        {
            if(v >= p[i].b)
            {
                v-=p[i].a;
            }
            else
                break;
        }
        if(i == n)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}