首页 > 代码库 > UVa 1152 和为0的4个值(二分查找)

UVa 1152 和为0的4个值(二分查找)

 

https://vjudge.net/problem/UVA-1152

题意:给定4个n元素集合A,B,C,D,要求分别从中选取一个元素a,b,c,d,使得a+b+c+d=0。问有多少种取法。

思路:直接暴力枚举的话是会超时的。可以选把a+b的值枚举出来存储,c和d的值也一样并排序,这样就可以在c和d中进行二分查找了。

 1 #include<iostream>   2 #include<algorithm> 3 using namespace std; 4  5 const int maxn = 4000 + 5; 6  7 int n; 8 int a[maxn], b[maxn], c[maxn], d[maxn]; 9 int s1[25000000], s2[25000000];10 11 12 void solve()13 {14     int k = 0;15     int cnt = 0;16     for (int i = 0; i < n; i++)17     {18         for (int j = 0; j < n; j++)19         {20             s1[k] = a[i] + b[j];21             s2[k] = c[i] + d[j];22             k++;23         }24     }25     sort(s2, s2 + k);26     for (int i = 0; i < k; i++)27     {28         int t = s1[i];29         int left = 0, right = k-1;30         while (left <= right)31         {32             int mid = (left + right) / 2;33             if (s2[mid] == -t)34             {35                 cnt++;36                 int p1 = mid;37                 int p2 = mid;38                 //因为有可能存在一样的数,所以前后还需要判断39                 while (s2[++p1] == -t && p1<k )  cnt++;40                 while (s2[--p2] == -t && p2>=0)  cnt++;41                 break;42             }43             else if (s2[mid]>-t)  right = mid-1;44             else left = mid+1;45         }46     }47     cout << cnt << endl;48 }49 50 int main()51 {52     //freopen("D:\\txt.txt", "r", stdin);53     int t;54     cin >> t;55     while (t--)56     {57         cin >> n;58         for (int i = 0; i < n; i++)59         {60             cin >> a[i] >> b[i] >> c[i] >> d[i];61         }62         solve();63         if (t)  cout << endl;64     }65     return 0;66 }

 

UVa 1152 和为0的4个值(二分查找)