4 Values whose Sum is 0(二分)
4 Values whose Sum is 0
Time Limit: 15000MS | Memory Limit: 228000K | |
Total Submissions: 21370 | Accepted: 6428 | |
Case Time Limit: 5000MS |
Description
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 228 ) 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).
Source
// 题意: 比如例子 6 行,每行 4 个数,从第一,二,三,四列各选一个数,要使和为 0 ,有几种组合?
n 最大有4000,但还是可以暴力,加二分
a + b = -( c + d )
枚举 a + b ,对于 c + d ,枚举一次,用一个大数组保存和,sort ,就可以二分了。要注意的是,二分到了要对左右继续搜索一下,不同的位置代表有不同的组合
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std; int n;
int k; int num[][];
int s[]; int erfen(int t)
{
int l=,r=k-;
while (l<=r)
{
int mid=(l+r)/;
if (s[mid]==t)
{
int e = mid-;
int all=;
while (e>=&&s[e]==t)
e--,all++;
e=mid+;
while (e<k&&s[e]==t)
e++,all++;
return all;
}
else if (s[mid]>t)
r=mid-;
else
l=mid+;
}
return ;
} int main()
{
while (scanf("%d",&n)!=EOF)
{
for (int i=;i<n;i++)
scanf("%d%d%d%d",&num[i][],&num[i][],&num[i][],&num[i][]);
k=;
for (int i=;i<n;i++)
for (int j=;j<n;j++)
s[k++]=-(num[i][]+num[j][]);
sort(s,s+k);
int total=;
for (int i=;i<n;i++)
{
for (int j=;j<n;j++)
{
int left=num[i][]+num[j][];
total+=erfen(left);
}
}
printf("%d\n",total);
}
return ;
}
最新文章
- ps 实例部分
- [C#详解] (1) 自动属性、初始化器、扩展方法
- 传说中的WeixinJSBridge和微信rest接口
- UVa 297 Quadtrees(树的递归)
- php实例根据ID删除mysql表中的数据
- debian 学习记录-1 -安装
- jquery插件--多行文本缩略
- Android 属性动画(二)
- nginx 配置文件解析(一)
- Shell 输入/输出重定向
- perl Socket接收超时设置
- iOS10适配——相机,通讯录,麦克风等权限设置
- 一篇深入剖析PCA的好文
- Linux定时器工具-crontab 各參数具体解释及怎样查看日志记录
- Hexo 搭建博客 本地运行 常见报错及解决办法
- python 路径处理
- oracle中in和exists的区别
- RavenDb学习(六)查询补充特性
- Python 字符串的相关操作
- HTTP返回代码 403 404 500等代表的含义
热门文章
- json格式在线解析
- Lock flag DX
- 2017.7.18 linux下用户、组和文件的操作
- 【Javascript 基础】使用数组
- iOS开发--Mac下server搭建
- 基于webmagic的种子网站爬取
- HDU4647:Another Graph Game(贪心)
- [linux]top命令详解-实时显示系统中各个进程的资源占用状况
- 如何为Apache JMeter开发插件(二)—第一个JMeter插件
- Storm/Cassandra集成错误:NoSuchMethodError: concurrent.Futures.withFallback