HDU 4334 Trouble (数组合并)
2024-10-21 14:42:14
Trouble
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5681 Accepted Submission(s):
1570
Problem Description
Hassan is in trouble. His mathematics teacher has given
him a very difficult problem called 5-sum. Please help him.
The 5-sum problem
is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is
there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?
him a very difficult problem called 5-sum. Please help him.
The 5-sum problem
is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is
there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?
Input
First line of input contains a single integer N
(1≤N≤50). N test-cases follow. First line of each test-case contains a single
integer n (1<=n<=200). 5 lines follow each containing n integer numbers in
range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.
(1≤N≤50). N test-cases follow. First line of each test-case contains a single
integer n (1<=n<=200). 5 lines follow each containing n integer numbers in
range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.
Output
For each test-case output "Yes" (without quotes) if
there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output
"No".
there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output
"No".
Sample Input
2
2
1 -1
1 -1
1 -1
1 -1
1 -1
3
1 2 3
-1 -2 -3
4 5 6
-1 3 2
-4 -10 -1
Sample Output
No
Yes
题意:t组数据,每组输入一个n,接下来有五行代表五个集合,每行n个数,问是否能从每个集合中找出一个数,
使得和为0。
题解:直接暴力会超时,将12两个集合合并,34两个集合合并,然后对他们进行从小到大排序,跑第五个集合。
用两个指针下标将12从小到大遍历,34逆序从大到小遍历,如果和<0,12集合的指针后移,如果和>0,
34集合的指针左移,如果和为0标记flag=1;break一下输出就行了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long a[],b[],c[],d[],e[],f[],g[];
long long i,j,x,k,l,n,t,flag=,p;
int main()
{
scanf("%lld",&t);
while(t--)
{
flag=;
//输入
scanf("%lld",&n);
for(i=;i<n;i++)
scanf("%lld",&d[i]);
for(i=;i<n;i++)
scanf("%lld",&e[i]);
for(i=;i<n;i++)
scanf("%lld",&f[i]);
for(i=;i<n;i++)
scanf("%lld",&g[i]);
for(i=;i<n;i++)
scanf("%lld",&c[i]);
//合并
int cnt1=;
for(i=;i<n;i++)
for(j=;j<n;j++)
a[cnt1++]=d[i]+e[j];
int cnt2=;
for(i=;i<n;i++)
for(j=;j<n;j++)
b[cnt2++]=f[i]+g[j]; //三四合并
sort(a,a+cnt1);
sort(b,b+cnt2);
//计算
for(i=;i<n;i++) //第五个数组 c[]
{
j=;
k=cnt2-;
while(j<cnt1 && k>=)
{
if(a[j]+b[k]+c[i]==0LL)
{
flag=;
break;
}
else if(a[j]+b[k]+c[i]<) //注意不要都写成i
j++;
else
k--;
} }
if(flag) cout<<"Yes"<<endl; //注意是Yes不是YES也不是yes
else cout<<"No"<<endl;
}
return ;
}
最新文章
- 多线程编程-工具篇-BlockingQueue
- 【Android UI】Android Layout XML属性
- NSArray倒序
- iOS本地数据存储(转载)
- 【Linux程序设计】之环境系统函数综合实验
- JOptionPanel类的解析
- ICE学习第四步-----客户端请求服务器返回数据
- CDZSC_2015寒假新人(1)——基础 a
- redis 编译安装(生产环境推荐)
- Nginx接收的host值会影响alias的规则匹配
- Python量化交易
- 数据库-mysql命令
- unresolved external symbol boost::throw_exception
- 译:3.消费一个RESTful Web Service
- windows WTL使用命令行参数
- 什么是.Net, IL, CLI, BCL, FCL, CTS, CLS, CLR, JIT
- hdu5230
- 联通营业厅API 获取个人信息
- MySQL慢查询优化
- Phaser Matter Collision Plugin 碰撞插件 -- iFiero技术分享