Repair the Wall

2024-01-13 19:38
文章标签 repair wall

本文主要是介绍Repair the Wall,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题 D: Repair the Wall

时间限制: 1 Sec   内存限制: 32 MB

题目描述


Long time ago , Kitty lived in a small village. The air was fresh and the scenery was very beautiful. The only thing that troubled her is the typhoon.
When the typhoon came, everything is terrible. It kept blowing and raining for a long time. And what made the situation worse was that all of Kitty's walls were made of wood.
One day, Kitty found that there was a crack in the wall. The shape of the crack is 
a rectangle with the size of 1×L (in inch). Luckly Kitty got N blocks and a saw(锯子) from her neighbors.
The shape of the blocks were rectangle too, and the width of all blocks were 1 inch. So, with the help of saw, Kitty could cut down some of the blocks(of course she could use it directly without cutting) and put them in the crack, and the wall may be repaired perfectly, without any gap.
Now, Kitty knew the size of each blocks, and wanted to use as fewer as possible of the blocks to repair the wall, could you help her ?



输入

The problem contains many test cases, please process to the end of file( EOF ).
Each test case contains two lines.
In the first line, there are two integers L(0<L<1000000000) and N(0<=N<600) which
mentioned above.
In the second line, there are N positive integers. The ith integer Ai(0<Ai<1000000000 ) means that the ith block has the size of 1×Ai (in inch).

输出

For each test case , print an integer which represents the minimal number of blocks are needed.
If Kitty could not repair the wall, just print "impossible" instead.

样例输入

2 2
12 11 
14 3
27 11 4 
109 5
38 15 6 21 32 
5 3
1 1 1

样例输出

1
1
5
impossible
#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{return a>b;
}
int main()
{int l,n;while(scanf("%d%d",&l,&n)!=EOF){int an[605]={0},sum=0,num=0;for(int i=0;i<n;i++){scanf("%d",&an[i]);sum+=an[i];}if(sum<l){printf("impossible\n");continue;}if(sum==l){printf("%d\n",n);continue;}sum=0;sort(an,an+n,cmp);for(int i=0;i<n;i++){sum+=an[i];if(sum>=l){printf("%d\n",i+1);break;}                }}return 0;
}

这篇关于Repair the Wall的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/602562

相关文章

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

P4560 [IOI2014] Wall 砖墙

*原题链接* 做法:线段树 一道比较基础的线段树练手题,区间赋值,在修改时加些判断剪枝。 对于add操作,如果此时区间里的最小值都大于等于h的话,就没必要操作,如果最大值都小于h的话,就直接区间赋值为h。对于remove操作同理。 时间复杂度大致为,实际会比这个要大一些。 #include<bits/stdc++.h>using namespace std;const int N=2

POJ 3691 HDU 2457 DNA repair (AC自动机,DP)

http://poj.org/problem?id=3691 http://acm.hdu.edu.cn/showproblem.php?pid=2457 DNA repair Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 5690 Accepted: 2669 Description Biologists

Repair LED lights

Repair LED lights  修理LED灯,现在基本用灯带,就是小型LED灯串联一起的 1)拆旧灯条,这个旧的是用螺丝拧的产品 电闸关掉。 2)五金店买一个,这种是磁铁吸附的产品 现在好多都是铝线啊。。。 小部件,我没用上

POJ--3253 -- Fence Repair

Fence Repair   Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 19763   Accepted: 6269 Description Farmer John wants to repair a small length of the fence around t

Codeforces 398B Painting The Wall(dp)

题目链接:Codeforces 398B Painting The Wall 题目大意:给出n和m,表示在一个n*n的平面上有n*n个瓷砖,其中有m块已经涂色。现在随机选中一块进行涂色(如果已经涂色跳过,也消耗时间),消耗1个步骤。终止条件为每行每列都有至少有一块瓷砖被涂色。问说涂成满意的情况需要时间的期望。 解题思路:现场出不来这道题,看来练的还是太少。题目可以理解成行涂n行,列

uva 1303 - Wall(凸包)

题目链接:uva 1303 - Wall 求出凸包加个圆周。 #include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <complex>#include <algorithm>using namespace std;typedef pair<int,int> pii;

UVA 1045 - The Great Wall Game(二分图完美匹配)

UVA 1045 - The Great Wall Game 题目链接 题意:给定一个n*n的棋盘,有n个棋子在上面,现在要移动棋子,每一步代价是1,现在要把棋子移动到一行,一列,或者在主副对角线上,问最小代价 思路:二分图完美匹配,枚举每种情况,建边,边权为曼哈顿距离,然后km算法做完美匹配算出值即可,由于要求最小值所以边权传负数,这样做出来的值的负就是答案 代码: #

1.-Os -Wall -Werror

在Makefile编译中,如果加上-Os -Wall -Werror,则可以防止函数定义未使用,当定义未使用时,会报错,而不是警告,保证了程序的正确运行. 还可以将程序中所有的warning都指示成为error,防止程序因为warning造成程序的不稳定性. 但是当打印调试时,需要取消.否则程序会编译不过去而出错. 举例: gcc main.c -Os -Wall -Werror -o

错误Incorrect key file for table ‘.\表名.MYI‘; try to repair it的解决办法

在mysql命令行运行check table xxx(表名); 如果存在问题 运行repair table xxx(表名)