3抽签

题意

n张写有数字的卡片，有放回地抽4次；
存在4次的数字之和为m的方案输出Yes，否则输出No

注：本题用到了二分搜索，如果简化的话，algorithm库文件里有binary_search(a,a+n,num)函数，返回的是bool类型

思路

思路一：四重循环，暴力搜索，复杂度过高n的4次方

思路二：三重循环，最后一个做差后二分搜索，复杂度n的3次方*logn

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a[60],n;
bool ersearch(int k)
{
    int left=0,right=n-1,i;
    while(left<=right-1)
    {
        i=(left+right)/2;
        if(a[i]==k) return true;
        else if(a[i]>k)
            right=i;
        else
            left=i+1;//注意因为是范围小了，所以是加1
    }
    return false;
}
int main()
{
    int sum,m,fl=0;
    cin>>n>>sum;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n&&fl==0;i++)
        for(int j=i+1;j<n&&fl==0;j++)
            for(int k=j+1;k<n&&fl==0;k++)
        {
            if(ersearch(sum-a[i]-a[j]-a[k]))
                {fl=1;break;}
        }
    if(fl==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}
思路三：二重循环，后两个为相加，后二分。n方logn

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a[60],n,b[2600];
bool ersearch(int k)
{
    int left=0,right=n*n-1,i;
    while(left<=right-1)
    {
        i=(left+right)/2;
        if(b[i]==k) return true;
        else if(b[i]>k)
            right=i;
        else
            left=i+1;//注意因为是范围小了，所以是加1
    }
    return false;
}
int main()
{
    int sum,m,fl=0;
    cin>>n>>sum;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            b[j+i*n]=a[i]+a[j];
    for(int i=0;i<n&&fl==0;i++)
        for(int j=i+1;j<n&&fl==0;j++)
        {
            if(ersearch(sum-a[i]-a[j]))
                {fl=1;break;}
        }
    if(fl==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

3抽签

原文：https://www.cnblogs.com/Joe2019/p/13348249.html