首页 > 代码库 > 挑战程序1.6.3(2)算法

挑战程序1.6.3(2)算法

 

题目:有n张纸片,随机取4张(可放回),如4张面值加起来可等于m,则输出yes,否则no。纸片的面值为k[1],k[2]……

思路:

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 bool ss(int x);
 5 void solve();
 6     int n,m,r,k[500];
 7     int kk[500];
 8     bool f;
 9 int main()
10 {
11     while(scanf("%d %d",&n,&m)!=EOF)
12     {
13         for(int i=0;i<n;i++)
14             scanf("%d",&k[i]);
15         solve();
16         if(f) printf("Yes\n");
17         else printf("NO\n");
18     }
19     return 0;
20 }
21 
22 void solve()
23 {
24     for(int a=0;a<n;a++)
25         for(int b=0;b<n;b++)
26         kk[a*n+b]=k[a]+k[b];
27          sort(kk,kk+n*n);
28           f=false;
29     for(int c=0;c<n;c++)
30         for(int d=0;d<n;d++)
31         if(ss(m-k[c]-k[d]))
32        {
33          f=true;
34        }
35 }
36 
37 bool ss(int x)
38 {
39     int l=0;r=n*n;
40     while(r-l>=1)
41     {
42         int i=(r+l)/2;
43         if(kk[i]>x)l=i+1;
44         else if (kk[i]==x) return true;
45         else r=i;
46     }
47 }

 

挑战程序1.6.3(2)算法