Day3-J-4 Values whose Sum is 0 POJ2785
2024-08-29 22:41:49
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 45
Sample Output
5
Hint
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).
思路:直接暴力的复杂度是N^4,肯定不行,可以两两合并,复杂度就是N^2,代码如下:
vector<int> buf[];
vector<long long>sum1,sum2; int main() {
int N,sum = ;
scanf("%d",&N);
for(int i = ; i < N; ++i) { // read
for(int j = ; j < ; ++j) {
int tmp;
scanf("%d",&tmp);
buf[j].push_back(tmp);
}
}
for(int i = ; i < N; ++i) {
for(int j = ; j < N; ++j) {
sum1.push_back(buf[][i] + buf[][j]);
sum2.push_back(buf[][i] + buf[][j]);
}
}
sort(sum1.begin(), sum1.end());
sort(sum2.begin(), sum2.end()); for(int i = ;i < sum1.size(); ++i) {
long long tmp = -sum1[i];
sum += upper_bound(sum2.begin(), sum2.end(), tmp) - lower_bound(sum2.begin(), sum2.end(), tmp);
}
printf("%d",sum);
return ;
}
最新文章
- C++ 第一次课堂作业
- OpenGLES入门笔记三
- angularJs中将字符串转换为HTML格式
- 网站开发常用jQuery插件总结(六)关键词说明插件cluetip
- winform windowsmediaplayer的属性
- Wix学习整理(2)——HelloWorld安装添加UI
- .Net C# Windows Service于server无法启动,错误 193:0xc1
- Knockout应用开发指南 第三章:绑定语法(3)
- BCB实现BMP图片的RGB分解(转)
- str-字符串功能介绍
- 最近找java实习面试被问到的东西总结(Java方向)
- Codeforce A. Quasi-palindrome
- JavaScript基础笔记(十)表单脚本
- 容器101:Docker基础
- linux编写.sh脚本并赋权限
- HNOI2019 白兔之舞 dance
- S3C2440串口的基本使用
- xcode显示行号show gutter
- (转,记录用)jQuery页面加载初始化的3种方法
- Spring源码加载过程图解(一)