傳送門：http://poj.org/problem?id=2785

解題思路：

從這四個(gè)數(shù)列中選擇的話總有n的4次方中情況，所以全部判斷一遍不可行。不過將他們對(duì)半分成AB和CD再考慮的話就可以解決了。從兩個(gè)數(shù)列中選擇的話只有n的2次方中組合。所以可以枚舉。從A，B中取出a，b后，為了使總和為0則需要從C，D中取出a+b=-（c+d）；先將a和b數(shù)組的和存在一個(gè)數(shù)組ab里面，再將c和d相加的相反數(shù)-（c+d）在ab數(shù)組里面查找，用的是二分查找。

實(shí)現(xiàn)代碼：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;const int MAXN=4005;int a[MAXN][4]; int b[MAXN*MAXN];void solve(int n){memset(b,0,sizeof(b));for(int i=0;i<n;i++)for(int j=0;j<n;j++)b[i*n+j]=a[i][0]+a[j][1];sort(b,b+(n*n));int ans=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++){int tmp=-(a[i][2]+a[j][3]);ans+=upper_bound(b,b+(n*n),tmp)-lower_bound(b,b+(n*n),tmp);}printf("%d\n",ans);}int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++)for(int j=0;j<4;j++)scanf("%d",&a[i][j]);solve(n); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/IKnowYou0/p/6665104.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的POJ 2785 4 Values whose Sum is 0的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。