C - 啥~ 渣渣也想找玩数字 HDU - 2141（有序序列枚举 + 二分优化查找）

题目描述可爱的演演又来了，这次他想问渣渣一题。。。如果给你三个数列 A[],B[],C[]，请问对于给定的数字

X，能否从这三个数列中各选一个，使得A[i]+B[j]+C[k]=X？

输入多组数据，你应处理到 EOF。每组数据的第一行是三个数 L, M, N，分别代表数列 A[],B[],C[]

的长度，接下来三行，每行分别是L, M, N 个数，分别代表数列 A[], B[], C[]。

接下来一行包含一个数S，代表有S组询问。之后的S行每行一个数，代表这组询问的 X。 1<=L, N, M<=500, 1<=S<=1000

；所有的数都在 32 位整数范围内。

输出首先对于每组数据输出一行“Case T: ”,T代表数据组数。然后每行对应一组询问，如果能够找到一组满足题目所述条件，输出

YES，否则输出 NO。

样例输入

3 3 3

1 2 3

1 2 3

1 2 3

3

1

4

10

样例输出

Case 1:

NO

YES

NO

思路

[ ] 题意：给我们三个序列A[] B[] C[ ]长度长度分别是 a，b，c，问能否在这三个序列中分别找一个数，使它的和相加等于定值x
[ ] 分析：这一题两层for循环一定会炸，所以我们要想办法去优化---->请看代码注释

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int mxn = 505;

int main()

{

    /* freopen("A.txt","r",stdin); */

    int m, n, k;

    int a[mxn], b[mxn], c[mxn], d[mxn * mxn];

    int Case = 0;

    while(scanf("%d %d %d", &m, &n, &k) != EOF)

    {

        for(int i = 1; i <= m; i ++)

            scanf("%d", &a[i]);

        for(int i = 1; i <= n; i ++)

            scanf("%d", &b[i]);

        for(int i = 1; i <= k; i ++)

            scanf("%d", &c[i]);

        int cnt = 0;

        //统计出来所有a、b序列元素相加可能的和

        for(int i = 1; i <= m; i ++)

            for(int j = 1; j <= n; j ++)

                d[cnt ++] = a[i] + b[j];

        sort(d, d + cnt);

        int q, x;

        scanf("%d", &q);

        printf("Case %d:\n", ++ Case);

        while(q --)

        {

            scanf("%d", &x);

            int flag = 0;

            for(int i = 1; i <= k; i ++)

            {

                int l = 0, r = cnt - 1, mid;

                //二分去在c中查找某个值使 c[i] + d[mid]== x

                while(l <= r)

                {

                    mid = (l + r) >> 1;

                    if(c[i] + d[mid] == x)

                    {

                        flag = 1; break;

                    }

                    else if(c[i] + d[mid] < x)

                    {

                        l = mid + 1;

                    }

                    else

                    {

                        r = mid - 1;

                    }

                }

                if(flag)

                    break;

            }

            if(flag)

                printf("YES\n");

            else

                printf("NO\n");

        }

    }

    return 0;

}

巴特西

C - 啥~ 渣渣也想找玩数字 HDU - 2141（有序序列枚举 + 二分优化查找）

思路

代码

最新文章

热门文章