链接: http://poj.org/problem?id=2785
设一个数组CD,储存C+D的所有和,。
再用二分搜索在CD中查找 -(A[i]+B[i] ) 的所有情况
#include <iostream> #include <algorithm> #define MAX_N 4000 using namespace std; int n; int A[MAX_N+5],B[MAX_N],C[MAX_N],D[MAX_N]; int CD[MAX_N*MAX_N]; void solve() { for(int i=0; i<n; i++) for(int j=0; j<n; j++) CD[i*n+j]=C[i]+D[j]; sort(CD,CD+n*n); long long res=0; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { int cd=-(A[i]+B[j]); res+=upper_bound(CD,CD+n*n,cd)-lower_bound(CD,CD+n*n,cd); } cout<<res<<endl; } int main() { while(cin>>n) { for(int i=0; i<n; i++) cin>>A[i]>>B[i]>>C[i]>>D[i]; solve(); } return 0; }