首页 > 代码库 > hdoj 2124 Repair the Wall 【贪心】

hdoj 2124 Repair the Wall 【贪心】

题意:有一栋墙坏了(台风吹坏的,并且宽度一定),这个猪脚要修这栋墙,并且找到了一些宽度跟刮坏的墙一样,只是长度不一样的木块,让你求这些木块能不能修好这堵墙,

一句话就是判断这些的木块的长度的和能不能大于破坏的墙的长度,如果能,输出最少用几块, 不能输出impossible。


这道题水的不行。。。从大到小排下序就好了

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2124

代码:

#include<stdio.h>
#include<algorithm>
using std::sort;
int s[700];
int main()
{
	int l, n, i, ans, sum;
	while(scanf("%d%d", &l, &n) == 2){
		for(i = 0; i < n; i ++)
			scanf("%d", &s[i]);
		sort(s, s+n);
		sum = 0;
		ans = 0;
		int flag = 0;
		for(i = n-1; i >= 0; i --){
			sum+= s[i];
			++ans;
			if(sum >= l){
				flag = 1;
				break;
			}
		}
		if(!flag)
		printf("impossible\n");
		else
		printf("%d\n", ans);
	}
	return 0;
}