Codevs No.2144 砝码称重2

2016-05-31 22:01:16

题目链接: 砝码称重2 (Codevs No.2144)

题目大意:

  给定N个砝码,求称出M的重量所需砝码最小个数

解法:

  贪心

  使砝码数量最小,当然是每个砝码越大越好

  首先排序,从大砝码开始试,遇到的第一个解一定最优

需要注意的地方:

  1.这道题的数据还是很给力的,裸贪心过不了,要加一个前缀和判断可达性进行优化

 //砝码称重2 (Codevs No.2144)
//贪心
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=;
long long N,M;
int ans;
int tmp;
long long a[maxn];
long long sum[maxn];
bool DFS(int x,long long val,int step)
{
if(val==)
{
ans=step;
return ;
}
for(int i=x;i>=;i--)
{
if(val-sum[i]>)break;
if(val-a[i]>=)
{
tmp=DFS(i-,val-a[i],step+);
if(tmp)return ;
}
}
return ;
}
int main()
{
scanf("%d %lld",&N,&M);
for(int i=;i<=N;i++)
{
scanf("%lld",&a[i]);
}
sort(a+,a+N+);
for(int i=;i<=N;i++)
{
sum[i]=sum[i-]+a[i];
}
DFS(N,M,);
printf("%d",ans);
}
上一篇:maven配置Mac平台


下一篇:十天精通CSS3(3)