[51nod] 1090 3个数和为0 暴力+二分
2024-10-29 15:33:50
给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等。从中找出所有和 = 0的3个数的组合。如果没有这样的组合,输出No Solution。如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则按照第二小的数排序。
Input
第1行,1个数N,N为数组的长度(0 <= N <= 1000)
第2 - N + 1行:A[i](-10^9 <= A[i] <= 10^9)
Output
如果没有符合条件的组合,输出No Solution。
如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则继续按照第二小的数排序。每行3个数,中间用空格分隔,并且这3个数按照从小到大的顺序排列。
Input示例
7
-3
-2
-1
0
1
2
3
Output示例
-3 0 3
-3 1 2
-2 -1 3
-2 0 2
-1 0 1 二重循环+二分 O(N^2LogN)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std; int a[]; bool binary_find(int l, int r, int x)
{
while (l <= r) {
int m = (l+r)>>;
if (a[m] > x)
r = m - ;
else if (a[m] < x)
l = m + ;
else
return ;
}
return ;
} int main()
{
//freopen("1.txt", "r", stdin);
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
sort(a, a+n);
int flag = ;
for (int i = ; i < n; i++) {
for (int j = i+; j < n; j++) {
int x = -(a[i]+a[j]);
// printf("%d %d %d\n", a[i], a[j], x);
if (binary_find(j+, n-, x)) {
printf("%d %d %d\n", a[i], a[j], x);
flag = ;
}
}
}
if (!flag) printf("No Solution\n"); return ;
}
更快的二分 同时搜索两个数
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std; int a[]; int main()
{
//freopen("1.txt", "r", stdin);
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
sort(a, a+n); int flag = ;
for (int i = ; i < n; i++) {
int j, k, x;
j = i+;
k = n-;
while (j < k) {
x = a[i]+a[j]+a[k];
if (x < )
j++;
else if (x > )
k--;
else {
printf("%d %d %d\n", a[i], a[j], a[k]);
flag = ;
j++; k--;
}
}
}
if (!flag) printf("No Solution\n"); return ;
}
最新文章
- HBase的Write Ahead Log (WAL) —— 整体架构、线程模型
- Core Foundation框架
- openerp child_of操作符深度解析
- poj 2777
- java ee 面试时的机试题
- Html-Css-iframe的使用
- 搭建SpringMVC+MyBatis开发框架四
- 测试xss和xsf
- JAVA 面试整理,面试汇总
- cocos2d-x创建场景
- C#设计模式之简单工厂模式
- [UIKit学习]07.关于如何选择UIButton、UILable、UIImageView
- R-CNN,SPP-NET, Fast-R-CNN,Faster-R-CNN, YOLO, SSD, R-FCN系列深度学习检测方法梳理
- 大华等其他NVR接入海康IPC H.264方法
- Ubuntu 14.04 LTS 下使用源码编译安装 Sagemath 6.7 x64 (小结)
- ELK实时日志分析平台环境部署--完整记录(转)
- P2704 [NOI2001]炮兵阵地
- j2ee数据库连接池配置大全
- Linux man 命令
- ACTGame项目