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);
}