HDU3177 Crixalis's Equipment 贪心

     该题给定一个容器的体积，以及N个物品，每个物品有其要求的最少空间以及实际所占的空间 。 要我们判断是否可以把所有的物品全部放在里面，当然如果能够放进去也是需要一定的顺序的。最好的放置方法就是每次将物品中所占空间与实际空间差值最大的首先放进去。

　　现在我们来证明这个差值排序的正确性：

　　先申明几个变量的符号： CUR_MAX_V  当前的最大体积 ； CUR_NULL_V  当前的空余的体积 ；T_MAX_V  当前物品的所需的体积 ;  T_REAL_V  当前物品的实际体积

现在假设有一个无限大的空间，保证能够将所有的物品放入，考虑到当前的体积与即将放入的物品有如下关系：

                                                                    （ CUR_MAX_V ）      (   T_MAX_V <=  CUR_NULL_V )

　　　　　　　　　　                CUR_MAX_V=

                                                                    （ CUR_MAX_V ）+ （ T_MAX_V ）- （ CUR_NULL_V ）      (  T_MAX_V >  CUR_NULL_V  )

　　由上式可知，要想使得CUR_MAX_V 在放入所有物品的同时尽可能的小则要求  CUR_NULL_V  足够大，因此我们总是选择将差值最大的首先放入，如果在这种最优的条件下都无法使得物品全部放入，则一定不能完成放入任务。

代码如下：

#include <stdio.h>
#include <stdlib.h>

struct Node
{
	int p;
	int v;
	int dec;
}N[1005];

int cmp( const void *a, const void *b )
{
	struct Node *x= ( struct Node * )a, *y= ( struct Node * )b;
	return y-> dec- x-> dec;
}

int main(  )
{
	int T;
	scanf( "%d", &T );
	while( T-- )
	{
		int ta, M, flag= 0;
		scanf( "%d %d", &ta, &M );
		for( int i= 0; i< M; ++i )
		{
			scanf( "%d %d", &N[i]. p, &N[i]. v );
			N[i]. dec= N[i]. v- N[i]. p;
		}
		qsort( N, M, sizeof( N[0] ), cmp );
		for( int i= 0; i< M; ++i )
		{
			if( ta>= N[i]. v )
			{
				ta-= ( N[i]. p);
			}
			else
			{
				flag= 1;
				break;
			}
		}
		printf( flag? "No\n": "Yes\n" );
	}
	return 0;
}