首页 > 代码库 > 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个值(二分查找)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。