Description
题目：
你的朋友提议玩个游戏：将写有数字的n个纸片放入口袋，你可以从口袋中抽取4次纸片，每次记下纸片上的数字后都将其放回口袋中。如果4个数字的和为m，就是你赢，否则就是你的朋友赢。你挑战了好几回，结果一次也没赢过，于是你怒而撕破口袋，取出所有纸片，检查自己是否真的有赢的可能性。请你编写一个程序，判断当纸片上所写的数字是k1，k2,...,kn时，是否存在抽取4次和为m的方案。若存在，输出yes；否则输出no
输入：n=3,m=9,k={1,3,5}
输出：NO
解题思路：
先通过排序把输入数组给从小（大）排列好，
然后再用二分法用来判断差值是否满足。
理论上来说应该是分治法更快，因为时间复杂度更低（n^3logn），但是我这弱鸡电脑都是跑到8个签就停止运行了，再者写了个排序算法导致运行速度大减。
基础算法：时间复杂度（n^3logn）
int algorithm (int k[])//基本算法
{
int p,q;
for(int a=0;a<n;a++)
for(int b=0;b<n;b++)
for(int c=0;c<n;c++)
{
z=m-k[a]-k[b]-k[c];
if(1==points(k,z))//分治
v=1;
}
分治法：
int points(int k[],int z)//分治
{
int l=0,r=n;
while(r-l>=1)
{
int i=(l+r)/2;
if(k[i]==z) return true;
else if(k[i]<z) l=i+1;
else r=i;
}
}
排序算法：
int array(int k[])//小到大排序
{
int i,l;
for(i=0;i<n;i++)
for(l=i+1;l<n;l++)
if(k[i]>k[l])
{ k[i]^=k[l];k[l]^=k[i];k[i]^=k[l];}//交换数据
}
具体算法：
#include<stdio.h>
int n,m,z,v=0;//n表示个数，m表示总值，z表示与总值的差值
int enter()
{
printf("分输入抽签个数，需要抽到的总值，与抽签的具体值\n");
scanf("%d",&n);//输入纸条个数
scanf("%d",&m);//需要求出的值
}
int array(int k[])//小到大排序
{
int i,l;
for(i=0;i<n;i++)
for(l=i+1;l<n;l++)
if(k[i]>k[l])
{ k[i]^=k[l];k[l]^=k[i];k[i]^=k[l];}//交换数据
}
int points(int k[],int z)//分治
{
int l=0,r=n;
while(r-l>=1)
{
int i=(l+r)/2;
if(k[i]==z) return true;
else if(k[i]<z) l=i+1;
else r=i;
}
}
int algorithm (int k[])//基本算法
{
int p,q;
for(int a=0;a<n;a++)
for(int b=0;b<n;b++)
for(int c=0;c<n;c++)
{
z=m-k[a]-k[b]-k[c];
if(1==points(k,z))//分治
v=1;
}
}
main()
{
int k[n];
enter();
for(int i;i<n;i++)
scanf("%d",&k[i]);
array(k);//排序算法
algorithm(k);//基本算法
if(v==1)
printf("Yes");
else
printf("No");
return 0;
}