hdu 2141 二分

hdu 2141 二分

題意是給你三個數組 分別有n m k個數 從三個數組裡分別拿一個數能不能等於s

剛開始沒注意數可以為負數 wa了好多次

別想直接暴力 肯定超時

現將兩個數組合並 暴力枚舉數少的 二分枚舉數多的（非常省時）

#include
#include
#include
using namespace std;
int main()
{
    int num1[510],num2[510],num3[510];
    int mark[300000];
    int i,j,k,p,d=1;
    int n,m;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++)
        scanf("%d",&num1[i]);
        for(i=1;i<=m;i++)
        scanf("%d",&num2[i]);
        p=0;
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        mark[++p]=num1[i]+num2[j];
        sort(mark+1,mark+1+p);
        for(i=1;i<=k;i++)
        scanf("%d",&num3[i]);
        sort(num3+1,num3+1+k);
        int s;
        scanf("%d",&s);
        printf("Case %d:\n",d++);
        while(s--)
        {
            int sum;
            scanf("%d",&sum);
            int flash=0;
            int left,right,mid;
            for(i=1;i<=k;i++)
            {
                left=1;
                right=p;
                while(left<=right)
                {
                    mid=(left+right)/2;
                    if(mark[mid]>sum-num3[i]) right=mid-1;
                    else if(mark[mid]<sum-num3[i]) left=mid+1;
                    else 
                    {
                        flash=1;
                        break;
                    }
                }
                if(flash) break;
            }
            if(flash) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}