hdu 3177

題目大意：向體積為v的山洞中搬運n個物品，每個物品具有(a,b) 屬性。其中a是停放體積，b是移動體積。輸出這個山東是否能放下這n個物品

解題思路：

1)當前物品能否放進山洞取決於當前物品的的移動體積是否小於山洞當前的剩余體積。

2)對這些物品進行排序 按照順序依次進入洞中 排序要盡可能使得所有的東西都能進入洞中

這是一個貪心的問題 

                                   停放體積         移動體積

                  第一件物品          a1             b1

                  第二件物品          a2             b2

假設這兩件物品的移動體積都不大於洞的體積V

那麼將單獨比較兩個物品的時候會發現  a1+b2為先放第一件物品 後放第二件物品的最大瞬時體積

                                                  a2+b1為先放第二件物品 後放第一件物品的最大瞬時體積

我們應該選擇a1+b2和a2+b1中比較小的先放

那麼從2件物品 擴展到N件物品 假設n件物品的移動體積都不大於洞的體積V(如果有大於的 那麼結果必然是NO)

將N件物品按照a1+b2<a2+b1進行排序 然後依次放入洞中

3)也就是說，每次向山洞中放移動體積和停放體積最大的那個物品

代碼如下：

/* 
 * 3177_2.cpp 
 * 
 *  Created on: 2013年8月10日 
 *      Author: Administrator 
 */  
  
#include <iostream>   
using namespace std;  
struct Node{  
    int f;  
    int l;  
};  
  
bool compare(Node a , Node b){  
    return a.f + b.l < b.f + a.l;  
}  
  
  
int main(){  
    int t;  
    scanf("%d",&t);  
  
    while(t--){  
        int v , n;  
        scanf("%d%d",&v,&n);  
        int i;  
        Node nodes[n];  
        for(i = 0 ; i < n ; ++i){  
            scanf("%d%d",&nodes[i].f,&nodes[i].l);  
        }  
  
        sort(nodes,nodes+n,compare);  
  
        bool flag = true;  
        for(i = 0 ; i < n ; ++i){  
            if(nodes[i].l > v){  
                printf("No\n");  
                flag = false;  
                break;  
            }else{  
                v -= nodes[i].f;  
            }  
        }  
  
  
        if(flag){  
            printf("Yes\n");  
        }  
  
    }  
}  

/*
 * 3177_2.cpp
 *
 *  Created on: 2013年8月10日
 *      Author: Administrator
 */

#include <iostream>
using namespace std;
struct Node{
	int f;
	int l;
};

bool compare(Node a , Node b){
	return a.f + b.l < b.f + a.l;
}


int main(){
	int t;
	scanf("%d",&t);

	while(t--){
		int v , n;
		scanf("%d%d",&v,&n);
		int i;
		Node nodes[n];
		for(i = 0 ; i < n ; ++i){
			scanf("%d%d",&nodes[i].f,&nodes[i].l);
		}

		sort(nodes,nodes+n,compare);

		bool flag = true;
		for(i = 0 ; i < n ; ++i){
			if(nodes[i].l > v){
				printf("No\n");
				flag = false;
				break;
			}else{
				v -= nodes[i].f;
			}
		}


		if(flag){
			printf("Yes\n");
		}

	}
}