首页 > 代码库 > HDU 2141 Can you find it?

HDU 2141 Can you find it?

2024-07-15 00:35:01   223人阅读

Problem 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，c，每个数组有若干个数（<=500个），再给定一个数s要你判断是否存在s=a[i]+b[j]+c[k]，存在一组数就输出YES，一组都不存在就输出NO。

思路：

A+B = X - C

先把a数组和b数组中的数相加成一个ab[500×500]的数组，这样就相当于ab[i]+c[j]=s;再变形一下，ab[i]=c[j]+s，只要在ab数组里用二分查找看能否把c[j]+s找出来。

 

 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define N 505 5  6 __int64 ab[N * N]; 7 int num; 8  9 bool _search(__int64 x)10 {11     int i = 0, l = num - 1;12     int mid;13     while(i <= l){14         mid = (i + l) / 2;15         if(ab[mid] == x)16             return true;17         else if(ab[mid] < x)18             i = mid + 1;19         else20             l = mid - 1;21     }22     return false;23 }24 25 int main()26 {27     int n, m, l, kase = 0, s;28     __int64 a[N], b[N], c[N], x;29     while(scanf("%d%d%d", &n, &m, &l) == 3){30         kase++; num = 0;31         for(int i = 0; i < n; i++)32             scanf("%I64d", &a[i]);33         for(int i = 0; i < m; i++)34             scanf("%I64d", &b[i]);35         for(int i = 0; i < l; i++)36             scanf("%I64d", &c[i]);37 38         for(int i = 0; i < n; i++)39             for(int j = 0; j < m; j++)40                 ab[num++] = a[i] + b[j];41         std::sort(ab, ab+num);42         std::sort(c, c+l);43 44         scanf("%d", &s);45         printf("Case %d:\n", kase);46         while(s--){47             scanf("%I64d", &x);48             if(x < ab[0] + c[0] || x > ab[num-1] + c[l-1])49                 printf("NO\n");50             else{51                 int flag = 0;52                 for(int i = 0; i < l; i++){53                     __int64 p = x - c[i];54                     if(_search(p)){55                         printf("YES\n");56                         flag = 1;57                         break;58                     }59                 }60                 if(!flag)61                     printf("NO\n");62             }63         }64     }65     return 0;66 }

 

 


联系
我们