首页 > 代码库 > hdu 2141 二分

hdu 2141 二分

题意是给你三个数组   分别有n m k个数     从三个数组里分别拿一个数能不能等于s

刚开始没注意数可以为负数    wa了好多次


别想直接暴力  肯定超时

现将两个数组合并  暴力枚举数少的      二分枚举数多的(非常省时)


#include<stdio.h>
#include<string.h>
#include<iostream>
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;
}

hdu 2141 二分