摘要：中途相遇。對比map，快排+二分查找，Hash效率。

?

n是4000的級別，直接O（n^4）肯定超，所以中途相遇法，O（n^2）的時(shí)間枚舉其中兩個(gè)的和，O（n^2）的時(shí)間枚舉其他兩個(gè)的和的相反數(shù)，然后O（logN）的時(shí)間查詢是否存在。

首先試了下map，果斷TLE

//TLE #include<cstdio> #include<algorithm> #include<map> using namespace std;const int maxn = 4001; int data[4][maxn];map<int,int> cnt;int main() {int T ; scanf("%d",&T);int *A = data[0], *B = data[1], *C = data[2],*D = data[3];map<int,int>::iterator it;while(T--){int n; scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d%d%d",A+i,B+i,C+i,D+i);}for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){cnt[A[i]+B[j]]++;}int ans = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){int tmp = -C[i]-D[j];it = cnt.find(tmp);if(it!=cnt.end()) ans += it->second;}printf("%d\n",ans);if(T) putchar('\n');}return 0; } map，TLE

然后改成了快排+二分查找，4920ms

// runtime 4920ms #include<cstdio> #include<algorithm> using namespace std;const int maxn = 4001; int data[4][maxn]; int vec[maxn*maxn];int _lower_bound(int *A,int L,int R,int v) {int m;while(L<R){m = (L+R)>>1;if(A[m]>=v) R = m;else L = m+1;}return L; }int _upper_bound(int *A,int L,int R,int v) {int m;while(L<R){m = (L+R)>>1;if(A[m]>v) R = m;else L = m+1;}return L; }int main() {int T ; scanf("%d",&T);int *A = data[0], *B = data[1], *C = data[2],*D = data[3];while(T--){int n; scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d%d%d",A+i,B+i,C+i,D+i);}int sz = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){vec[sz++] = A[i]+B[j];}sort(vec,vec+sz);int ans = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){int tmp = -(C[i]+D[j]);ans += _upper_bound(vec,0,sz,tmp) - _lower_bound(vec,0,sz,tmp);}printf("%d\n",ans);if(T) putchar('\n');}return 0; } 快拍+二分，4920ms

實(shí)際上沒有必要每次二分查找，用兩個(gè)指針，兩邊都從最小的數(shù)開始比較。

快排+計(jì)數(shù)，2832ms

#include<cstdio> #include<algorithm> #include<map> using namespace std; typedef pair<int,int> pii; #define fi first #define se second const int maxn = 4001; int data[4][maxn];pii cnt1[maxn*maxn]; pii cnt2[maxn*maxn]; int vec[maxn*maxn];int main() {int T ; scanf("%d",&T);int *A = data[0], *B = data[1], *C = data[2],*D = data[3];while(T--){int n; scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d%d%d%d",A+i,B+i,C+i,D+i);}int sz = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){vec[sz++] = A[i]+B[j];}sort(vec,vec+sz);int len1 = 0;cnt1[len1] = pii(vec[len1],1);for(int i = 1; i < sz; i++){if(vec[i] == cnt1[len1].fi) cnt1[len1].se++;else { cnt1[++len1].fi = vec[i]; cnt1[len1].se = 1; }}sz = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){vec[sz++] = -C[i]-D[j];}sort(vec,vec+sz);int len2 = 0;cnt2[len2] = pii(vec[len2],1);for(int i = 1; i < sz; i++){if(vec[i] == cnt2[len2].fi) cnt2[len2].se++;else { cnt2[++len2].fi = vec[i]; cnt2[len2].se = 1; }}int p = 0,q = 0,ans = 0;while(p<=len1&&q<=len2){if(cnt1[p].fi == cnt2[q].fi){ans += cnt1[p++].se*cnt2[q++].se;}else if(cnt1[p].fi>cnt2[q].fi) q++;else p++;}printf("%d\n",ans);if(T) putchar('\n');}return 0; } 快排+計(jì)數(shù)

還有Hash表，寫掛了，待補(bǔ)。。。

?

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

總結(jié)

以上是生活随笔為你收集整理的UVA 1152 4 Values Whose Sum is Zero 和为0的4个值 （中途相遇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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