51Nod 1267 4个数和为0 二分

时间:2022-09-07 14:25:47

给出N个整数,你来判断一下是否能够选出4个数,他们的和为0,可以则输出"Yes",否则输出"No"。
Input
第1行,1个数N,N为数组的长度(4 <= N <= 1000)
第2 - N + 1行:A[i](-10^9 <= A[i] <= 10^9)
Output
如果可以选出4个数,使得他们的和为0,则输出"Yes",否则输出"No"。
Input示例
5
-1
1
-5
2
4
Output示例
Yes
思路:
二分
第一次是枚举前两个数,后面两个数二分
第二次做法是,先统计出两个不同数的和的数组,然后直接二分

思路一:

 #include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans[];
int main() {
ios::sync_with_stdio(false);
int n,flag=;
cin>>n;
for(int i=;i<n;++i) cin>>ans[i];
sort(ans,ans+n);
for(int i=;i<n;++i) {
if(ans[i]>=) break;
for(int j=i+;j<n;++j) {
int l=j+,r=n-;
while(j<r) {
ll temp=ans[i]+ans[j]+ans[l]+ans[r];
if(temp>) r--;
else if(temp<) l++;
else {
flag=;
cout<<"Yes"<<endl;
return ;
}
}
}
}
if(!flag) cout<<"No"<<endl;
return ;
}

思路二:

 #include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
struct node {
ll sum,x,y;
node() {sum=x=y=;}
};
node bns[];
ll ans[];
bool cmp(const node &a, const node &b) {
if(a.sum<b.sum) return true;
if(a.sum>b.sum) return false;
if(a.x<b.x) return true;
if(a.x>b.x) return false;
if(a.y<=b.y) return true;
else return false;
}
int main() {
ios::sync_with_stdio(false);
int n,ins=;
cin>>n;
for(int i=;i<n;++i) cin>>ans[i];
for(int i=;i<n;++i) {
for(int j=i+;j<n;++j) {
bns[ins].sum=ans[i]+ans[j];
bns[ins].x=ans[i];
bns[ins].y=ans[j];
ins++;
}
}
sort(bns,bns+ins,cmp);
int l=,r=ins-,flag=;
while(l<r) {
ll temp=bns[l].sum+bns[r].sum;
if(temp<) l++;
else if(temp>) r--;
else {
if(bns[l].x!=bns[r].x&&bns[l].y!=bns[r].x&&bns[l].y!=bns[r].y) {
cout<<"Yes"<<endl;
flag=;
return ;
}
l++;
r--;
}
}
if(!flag) cout<<"No"<<endl;
return ;
}

51Nod 1267 4个数和为0 二分的更多相关文章

  1. 51nod 1267 4个数和为0

    基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 给出N个整数,你来判断一下是否能够选出4个数,他们的和为0,可以则输出"Yes",否则输出&qu ...

  2. &lbrack;51nod&rsqb; 1267 4个数和为0 暴力&plus;二分

    给出N个整数,你来判断一下是否能够选出4个数,他们的和为0,可以则输出"Yes",否则输出"No". Input 第1行,1个数N,N为数组的长度(4 < ...

  3. 51nod 1267 4个数和为0 思路:哈希map&plus;避免重复的点

    题目: 总结大佬们的思路: 思路1:所有数两两求和,存入map中,每次判断有没有相反数被标记过. 思路2:对所有数排序,排完所有数两两求和,结果正好是排好序的.然后扫一遍,二分查找看之前有没有相反数存 ...

  4. 51 nod 1267 4个数和为0

    1267 4个数和为0 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题  收藏  取消关注 给出N个整数,你来判断一下是否能够选出4个数,他们的和为0,可以则输出& ...

  5. 51nod 1090 3个数和为0【二分】

    1090 3个数和为0 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题  收藏  关注 给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等.从 ...

  6. 51Nod 1090 3个数和为0&lpar;暴力&rpar;

    1090 3个数和为0 基准时间限制:1 秒 空间限制:131072 KB 分值: 5         难度:1级算法题 给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等.从 ...

  7. 51Nod 1090 3个数和为0 set 二分优化

    给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等.从中找出所有和 = 0的3个数的组合.如果没有这样的组合,输出No Solution.如果有多个,按照3个数中最小的数从小到 ...

  8. &lbrack;51nod&rsqb; 1090 3个数和为0 暴力&plus;二分

    给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等.从中找出所有和 = 0的3个数的组合.如果没有这样的组合,输出No Solution.如果有多个,按照3个数中最小的数从小到 ...

  9. 51nod——T1267 4个数和为0

    https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1267 题目描述 给出N个整数,你来判断一下是否能够选出4个数,他们的和 ...

随机推荐

  1. apt-get update &colon; pulic key error

    apt-get update  出现 这种错误 Reading package lists... Done W: There is no public key available for the fo ...

  2. &lbrack;SDK2&period;2&rsqb;Windows Azure Cloud Service &lpar;35&rpar; 使用VS2013发布Azure Cloud Service

    <Windows Azure Platform 系列文章目录> 好久没有更新BLOG了,今天我们继续Windows Azure相关的内容. 笔者最近把Visual Studio升级到了20 ...

  3. common-pool2对象池&lpar;连接池&rpar;的介绍及使用

    我们在服务器开发的过程中,往往会有一些对象,它的创建和初始化需要的时间比较长,比如数据库连接,网络IO,大数据对象等.在大量使用这些对象时,如果不采用一些技术优化,就会造成一些不可忽略的性能影响.一种 ...

  4. java的软件包

    Java的软件包:简单来说,软件包就是把类放在不同的文件夹下,提供了命名空间 package wang; //用package将Test类放在wang文件下 class Test{ public st ...

  5. 翻译:《What can I hold you with&quest;》—— 博尔赫斯《英文诗两首》之一。

    What can I hold you with? 我拿什么才能留住你? I offer you lean streets, desperate sunsets, the moon of the ja ...

  6. 团队合作之项目NABCD

    小组组长 :毛松林 组员  :张浩,谢诗语 N 我们小组要开发的项目是“高校自习室查询APP”,作为一个大学生,自学是一件很重要的能力,大学的老师不可能还像高中的老师那样整天逼着你学习,爱学不学,不学 ...

  7. scapy学习笔记(3)发送包&comma;SYN及TCP traceroute 扫描

    转载请注明:@小五义:http://www.cnblogs/xiao* 在安装完scapy(前两篇笔记有介绍)后,linux环境下,执行sudo scapy运行scapy. 一.简单的发送包 1 ...

  8. &lbrack;javaSE&rsqb; 变量的传值与传址

    变量:就是将不确定的数据进行存储.也就是需要在内存中开辟一个空间 这个空间需要一个名称,这个名称就是变量名 基本数据类型:byte,short,int,long,double,float,char,b ...

  9. JAVA nio 2 定义 Path 类

    一旦确认了文件系统上的一个文件或目录,那么就可以定义一个 Path 类来指向它.定义 Path 类可以使用绝对路径.相对路径.路径中带有一个点号“.”(表示当前目录).路径中带有两个点“..”(表示上 ...

  10. &lbrack;转&rsqb; 基本RS触发器

    在触发器中,最简单的触发器是基本RS触发器,它由两个与-非门(或者两个或-非门)来组成. 图5.2.1(a)是由与-非门构成的基本RS触发器,由图看出,基本RS触发器有两个输入端(和)和两个输出端(和 ...