[HDU 4334] Trouble （分治+二分查找）

本文主要是介绍[HDU 4334] Trouble （分治+二分查找），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU - 4334
给你五个数组，每组 N个元素 (N<=200)
问是否能在五个数组里各选一个数，使得和为0
思路是分治，然后再二分查找，降低复杂度

1) 算出 $S_1$ 和 $S_2$ 所有元素的和的情况并排序，对 $S_3$ 和 $S_4$ 亦是如此 O( $N^2$ )
2) 枚举 $S_3$ 和 $S_4$ 的和数组与 $S_5$ 的和的情况
再在 $S_1$ 和 $S_2$ 的和数组里找其相反数 O( $N^2*N*log(N^2)$ )

所以最终时间复杂度就为 O( $N^3*log(N)$ )

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
#define pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}const int maxn=210;
int N;
LL inpt[2][maxn];
LL res[2][maxn*maxn];int Get(int);
bool Exist(int,int,LL);int main()
{int T;scanf("%d", &T);for(int ck=1; ck<=T; ck++){CLR(inpt);CLR(res);scanf("%d", &N);int siz1=Get(0);int siz2=Get(1);bool ok=0;for(int i=0; i<N; i++){LL now;cin>>now;for(int j=0; j<siz2; j++){if(ok) break;LL val=now+res[1][j];if(Exist(0,siz1,-val)){ok=1;break;}}}puts(ok?"Yes":"No");}return 0;
}int Get(int np)
{for(int i=0; i<N; i++) cin>>inpt[0][i];for(int i=0; i<N; i++) cin>>inpt[1][i];int siz=0;for(int i=0; i<N; i++){for(int j=0; j<N; j++){res[np][siz++]=inpt[0][i]+inpt[1][j];}}sort(res[np],res[np]+siz);siz=unique(res[np],res[np]+siz)-res[np];return siz;
}bool Exist(int np, int siz, LL val)
{int l=0,r=siz;while(l+1<r){int mid=(l+r)>>1;if(res[np][mid]==val) return 1;if(res[np][mid]>val) r=mid;else l=mid;}return 0;
}