二分-G - 4 Values whose Sum is 0
2024-10-08 09:47:35
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .Output
For each input file, your program has to write the number quadruplets whose sum is zero.Sample Input
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45Sample Output
5Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
题目大意:每行会给出四个整数,要求在每列整数中找出一个整数,使四个整数之和为0,求有几种不同组合
#include<iostream>
#include<algorithm>
using namespace std; const int maxn = ;
const int maxm = *;
int a[maxn],b[maxn],c[maxn],d[maxn];
int ab[maxm],cd[maxm]; int main(){
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d %d %d %d",a+i,b+i,c+i,d+i); int cnt = ;
for(int i=;i<n;i++)//前两列整数求和
for(int j=;j<n;j++)
ab[cnt++] = a[i] + b[j];
cnt = ;
for(int i=;i<n;i++)//后两列整数求和
for(int j=;j<n;j++)
cd[cnt++] = c[i] + d[j]; sort(ab,ab+n*n);
sort(cd,cd+n*n); int p = n*n-;
cnt = ;
for(int i=;i<n*n;i++){
for(;p>=;p--)
if(ab[i]+cd[p]<=) break;
if(p<) break;
for(int j=p;j>=;j--){
if(ab[i]+cd[j]==) cnt++;
if(ab[i]+cd[j]<) break;
}
}
printf("%d",cnt);
}
面对四列整数,一一组合将会造成极其庞大的数据,可将其中两两组合,组合以后再相加寻找和为0的情况。
最新文章
- ActiveReports中如何在后台导出运行时绑定数据源报表
- jboss eap 6.3 集群(cluster)配置
- android之ViewPager
- HDU 1160 FatMouse&#39;s Speed
- 用gd库画矩形和椭圆
- 【转载】ASP.NET线程安全与静态变量的生命周期浅谈
- PHP include 和 require
- asp.net DropDownList的AppendDataBoundItems属性
- iOS导航条渐变透明
- codechef Little Elephant and Permutations题解
- Ecstore1.2启用mongodb添加索引
- 某互联网后台自动化组合测试框架RobotFramework+Python+Sikuli
- 【转载】C#常用数据库Sqlserver通过SQL语句查询数据库以及表的大小
- SAP S4/HANA BP屏幕增强添加自定义字段(BDT方式)
- 嵌入式开发之hi3519---PCIE DMA
- python+selenium—webdriver入门(一)
- win10引导错误的修复(内容系转载)
- UINavigationController出现nested push animation can result in corrupted navigation bar的错误提示
- hdu 2063 匈牙利算法
- 三:SpringTransaction