HDU 4334 Trouble

时间：2024-01-17 13:39:20

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[][] ;

   LL A[*] ;

   LL B[*] ;

   LL C[] ;

   Me(){}

   Me(int n):N(n){}

   void read_init(){

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

       for(int j=;j<=N;j++)

          scanf("%I64d",&num[i][j]) ;

     int k ;

     k=;

     for(int i=;i<=N;i++)

        for(int j=;j<=N;j++)

           A[++k]=num[][i]+num[][j];

     k= ;

     for(int i=;i<=N;i++)

        for(int j=;j<=N;j++)

           B[++k]=num[][i]+num[][j];

     for(int i=;i<=N;i++)

         C[i]=num[][i] ;

   }

   int my_search(LL x){

       int i= ;

       int j=b_size ;

       while(i<=a_size&&j>=){

          if(A[i]+B[j]<x)

            i++ ;

          else if(A[i]+B[j]==x)

            return  ;

          else if(A[i]+B[j]>x)

            j-- ;

       }

       return  ;

   }

   int calc(){

      sort(A+,A++N*N) ;

      a_size=unique(A+,A++N*N)-(A+) ;

      sort(B+,B++N*N) ;

      b_size=unique(B+,B++N*N)-(B+) ;

      sort(C+,C++N) ;

      c_size=unique(C+,C++N)-(C+) ;

      for(int i=;i<=c_size;i++){

            if(my_search(-*C[i]))

                return  ;

      }

      return  ;

   }

   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  ;

}

相关文章