《挑战程序设计竞赛》例题：抽签（升级篇）

题目大意见第一篇文章,区别是n的范围由【1,50】变成了【1，1000】
分析：因为n范围变大了，而四重循环的时间复杂度为o( )将1000带入显然不行，会超时，考虑一下第四重循环的数可以有关系式得出k=m-a[i]-a[x]-a[y]，所以只要验证k是不是数组a中的一员就行了，这里我们采用二分法，二分法的时间复杂度是o(logn)所以总的时间复杂度是o( logn)(将1000带入也超过 )所以还要简化算法，这里我们将前两个循环合成一个循环，将前两个循环移出去，用一个数组装下他们所有的和也就是n*n个数，所以就有关系式:b数组中的某个数=m-a[i]-a[x],这下就只用两个循环了，时间复杂度大大降低
源代码如下：

三重循环的源码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;//n为口袋中纸的数目，m是要求的和，ki为某张纸上的数字
    cin>>n>>m;
    int a[n];//数组a为储存纸上数字的数组
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        for(int x=0;x<n;x++)
        {
            for(int y=0;y<n;y++)
            {
                if(binary_search(a,a+n,m-a[i]-a[x]-a[y]))//binary_search是c++ STL中的，进行二分查找模板binary_search（arr[],arr[]+n,x）arr[]为数组首地址，n为数组大小，x为想查找的数
                {
                    cout<<"yes"<<endl;//这里记得用b数组噢
                    return 0;//保证只输出一个yes，否则后面也可能出现符合的组合
                }

            }
        }
    }
    cout<<"no"<<endl;
}
二重循环的源码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;//n为口袋中纸的数目，m是要求的和，ki为某张纸上的数字
    cin>>n>>m;
    int a[n],b[n*n];//数组a为储存纸上数字的数组
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        for(int x=0;x<n;x++)
        {
            b[i*n+x]=a[i]+a[x];
        }
    }
    sort(b,b+n*n);
    for(int i=0;i<n;i++)
    {
        for(int x=0;x<n;x++)
        {
                if(binary_search(b,b+n*n,m-a[i]-a[x]))//binary_search是c++ STL中的，进行二分查找模板binary_search（arr[],arr[]+n,x）arr[]为数组首地址，n为数组大小，x为想查找的数
                {
                    cout<<"yes"<<endl;
                    return 0;//保证只输出一个yes，否则后面也可能出现符合的组合
                }

        }
    }
    cout<<"no"<<endl;
}