【二分】Can you find it?

传送:HDU 2141

Description
Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.
Input
There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.
Output
For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".
Sample Input
3 3 3

1 2 3

1 2 3

1 2 3

3

1

4

10
Sample Output

Case 1:

NO

YES

NO

题意:三个数组各取一个数,问能否加起来等于第四个数

分析:A+B=M-C 求出A+B的和,二分C,看能否满足条件

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
  long long l, m, n, cas = 1;
  while (cin >> l >> m >> n)
  {
    long long a[510], b[510], c[510], d[250010];
    for (int i = 0; i < l; i++)
      cin >> a[i];
    for (int i = 0; i < m; i++)
      cin >> b[i];
    for (int i = 0; i < n; i++)
      cin >> c[i];

    int k = 0;
    for (int i = 0; i < l; i++)
      for (int j = 0; j < m; j++)
        d[k++] = a[i] + b[j];
    sort(d, d + k);
    int s;
    cin >> s;
    printf("Case %d:\n", cas++);
    while (s--)
    {
      long long x;
      cin >> x;
      bool flag = false;
      for (int i = 0; i < n; i++)//第三个数组和新数组mid相加判断 
      {
        int l = 0, r = k - 1;
        while (l <= r)
        {
          int mid = (l + r) >> 1;
          if (d[mid] + c[i] == x)
          {
            flag = true;
            break;
          }
          else if (d[mid] + c[i] < x)
          {
            l = mid + 1;
          }
          else
            r = mid - 1;
        }
        if (flag)
          break;
      }
      if (flag)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
  return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

15 + 1 =