HDU 4334 Trouble

Trouble

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3526 Accepted Submission(s): 1113

Problem Description

Hassan is in trouble. His mathematics teacher has given him a very difficult problem called 5-sum. Please help him.
The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?

Input

First line of input contains a single integer N (1≤N≤50). N test-cases follow. First line of each test-case contains a single integer n (1<=n<=200). 5 lines follow each containing n integer numbers in range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.

Output

For each test-case output "Yes" (without quotes) if there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output "No".

Sample Input

2 2 1 -1 1 -1 1 -1 1 -1 1 -1 3 1 2 3 -1 -2 -3 4 5 6 -1 3 2 -4 -10 -1

Sample Output

No Yes

题意：

给定五个集合，从五个集合中分别取出5个数，如果存在满足a1 +a2 + a3 + a4 +a5 = 0

分析：

事实上考虑如下问题，快速求解序列A，序列B中，是否有Ai+Bj=x ,记得是某知名公司的一道面试题吧；

是两个指针的应用，将A，B升序排列，初试 i 指针指向A[1] ，j 指针指向 B[b_size] ,比较Ai + Bj 与 x 的

大小。若A[i]+B[j]<x , i 指针右移 ; 若 A[i]+B[j]>x , j 指针左移。事实上是一个贪心的思想。

个人感悟：

使用returen 比 break 好吧。

#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <set>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std ;
typedef long long LL ;
struct Me{
   LL N ,N_2 ,a_size ,b_size ,c_size;
   LL num[5][208] ;
   LL A[208*208] ;
   LL B[208*208] ;
   LL C[208] ;
   Me(){}
   Me(int n):N(n){}
   void read_init(){
     for(int i=0;i<=4;i++)
       for(int j=1;j<=N;j++)
          scanf("%I64d",&num[i][j]) ;
     int k ;
     k=0;
     for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
           A[++k]=num[0][i]+num[1][j];
     k=0 ;
     for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
           B[++k]=num[2][i]+num[3][j];
     for(int i=1;i<=N;i++)
         C[i]=num[4][i] ;
   }
   int my_search(LL x){
       int i=1 ;
       int j=b_size ;
       while(i<=a_size&&j>=1){
          if(A[i]+B[j]<x)
            i++ ;
          else if(A[i]+B[j]==x)
            return 1 ;
          else if(A[i]+B[j]>x)
            j-- ;
       }
       return 0 ;
   }
   int calc(){
      sort(A+1,A+1+N*N) ;
      a_size=unique(A+1,A+1+N*N)-(A+1) ;
      sort(B+1,B+1+N*N) ;
      b_size=unique(B+1,B+1+N*N)-(B+1) ;
      sort(C+1,C+1+N) ;
      c_size=unique(C+1,C+1+N)-(C+1) ;
      for(int i=1;i<=c_size;i++){
            if(my_search(-1*C[i]))
                return 1 ;
      }
      return 0 ;
   }
   void gao_qi(){
      read_init() ;
      if(calc())
        puts("Yes") ;
      else
        puts("No") ;
   }
};
int main(){
  int T ,N ;
  cin>>T ;
  while(T--){
    scanf("%d",&N) ;
    Me me(N) ;
    me.gao_qi() ;
  }
  return 0 ;
}