Description
给你N个整数，能不能从中找出几个数，使这几个数的和等于M
Input
第一行 给你t ,t表示有几组测试数据。
每组数据包括二行：第一行给你整数N(2＜N＜1000)，M(1＜=M＜=10000).第二行有N个数，且这N个数都小于M，两个数中间有一个空格隔开。
Output
每个测试只输出一行，不能有多余的空格。
如果可以得到和M，则输出“yes”；否则输出“no”。
Sample Input
2
6 10
1 2 3 4 5 6
6 40
2 4 6 8 10 1
Sample Output
yes
no
[此贴子已经被作者于2007-11-15 19:43:08编辑过]
----------------解决方案--------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
int compar(const void *a,const void *b)
{
int *aa=(int *)a,*bb=(int *)b;
return *bb-*aa;
}
int main()
{
int n,m,i,j,sum,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int base[n],flag=0;
for(i=0;i<n;i++)
scanf("%d",&base[i]);
qsort(base,n,sizeof(int),compar);
for(i=0;i<n;i++)
{
sum=m;
for(j=i;j<n;j++)
{
if(sum>=base[j]) sum=sum-base[j];
if(sum==0) { flag=1; break;}
}
}
if(flag==1) printf("yes\n");
else printf("no\n");
}
return 0;
}
----------------解决方案--------------------------------------------------------
我的AC了的 爽
----------------解决方案--------------------------------------------------------
你过了纯属意外..
你测试一下这个数据
1
4 23
13 9 7 3
似乎你的答案是:no.
23=13+7+3;
----------------解决方案--------------------------------------------------------
怎么办啊
----------------解决方案--------------------------------------------------------
你再想几组特殊数字看看 或者你有什么好的方法介绍一下
----------------解决方案--------------------------------------------------------
再看看这个
#include<stdio.h>
#include<stdlib.h>
int comp_ints(const void *p1,const void *p2)
{
int i1=*(int *)p1;int i2=*(int *)p2;
return i1-i2;
}
int main(void)
{
int i,j,j1,j2,n,m,t,isture,sum,l,count=0;
int a[1002];
scanf("%d",&t);
for(i=0;i<1002;i++)
a[i]=0;
for(i=0;i<t;i++)
{
isture=0;count=0;
sum=0;
scanf("%d%d",&n,&m);
for(j=0;j<n;j++)
scanf("%d",&a[j]);
qsort (a,n,sizeof(int),comp_ints);
n=n-1;
l=n;
for(j2=n;j2>=0;j2--)
{
l=j2;
while(l!=-1)
{
sum=0;
if(l!=j2)
sum+=a[n];
for(j1=l;j1>=0;j1--)
{
sum=sum+a[j1];
if(sum>=m)
{
if(sum==m)
{
isture=1;
break;
}
else
{
sum=sum-a[j1];
}
}
}
if(isture==1)
break;
l--;
}
if(isture==1)
break;
}
if(isture==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
----------------解决方案--------------------------------------------------------
我也没有想到太好的办法...
上次做了一个JOJ的题目和这个差不多.但是那里的m最大到10000,把那个思路直接用到这里来的话复杂度是1000*10000
1s内可能没有办法做到??
上次那个题目还有人用母函数的方法..但是估计复杂度也好不到哪里去..
----------------解决方案--------------------------------------------------------
JOJ是哪个学校的 把差不多的题的网址贴出来下 我看哈
----------------解决方案--------------------------------------------------------
感觉好难啊````给出的数据都好大啊````想到的第一个方法``一定超时```
好算法得再思考思考````
----------------解决方案--------------------------------------------------------