uva1152 - 4 Values whose Sum is 0(枚举,中途相遇法)
2024-09-08 10:56:16
用中途相遇法的思想来解题。分别枚举两边,和直接暴力枚举四个数组比可以降低时间复杂度。
这里用到一个很实用的技巧:
求长度为n的有序数组a中的数k的个数num?
num=upper_bound(a,a+n,k)-lower_bound(a,a+n,k);
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cctype>
#include<sstream>
using namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair<int,int>
#define LL long long int
#define maxn 4005
int T,n,A[maxn],B[maxn],C[maxn],D[maxn],sum[maxn*maxn];
int main()
{
//freopen("in8.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
}
int c=;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
sum[c++]=A[i]+B[j];
}
}
sort(sum,sum+c);
LL ans=;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
ans+=upper_bound(sum,sum+c,-C[i]-D[j])-lower_bound(sum,sum+c,-C[i]-D[j]);
//这一句是全篇的点睛之笔。
}
}
printf("%lld\n",ans);
if(T) printf("\n");
}
//fclose(stdin);
//fclose(stdout);
return ;
}
最新文章
- 分享公司DAO层数据库结果映射到对象的方法
- 基于webdriver的jmeter性能测试-Eclipse+Selenium+JUnit生成jar包
- XUtils3 的 环境搭建
- words in view Moqui resource code
- Function Scope
- Programs vs. processes
- SVG之初识
- Linux 命令 - killall: 通过进程名向进程发送信号
- 用Javascript进行HTML转义(分享)
- 打jar包的方法
- Android源代码同步脚本(增加设置线程参数)
- Memcached缓存
- scrapy爬取极客学院全部课程
- 原生js实现preAll和nextAll方法
- 20190326-HTML5标签、CSS的引用
- [Linux/Ubuntu] vi/vim 使用方法讲解
- WebStorm for Mac(Web 前端开发工具)破解版安装
- .NetCore 分页控件实现原理处理以及条件分页处理
- thinkphp3.2 session时间周期无效
- 【深度好文】多线程之WaitHandle-->;派生-》Mutex信号量构造