二分搜索-poj2785

题目链接:http://poj.org/problem?id=2785

题目大意:要求输入A,B,C,D四个数组,从每个数组中分别取出一个数来相加,求出相加后 和为0 总共有多少种加法。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=;
int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int AB[MAXN*MAXN];
int n;
int main()
{
long long res=;
while(~scanf("%d",&n))
{
for(int i=;i<n;i++)
{
scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
}
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
AB[i*n+j]=A[i]+B[j];//现将数组A+数组B中的元素相加,然后在对数组C,D进行相加
}
}
sort(AB,AB+n*n);
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
int cd=-(C[i]+D[j]);
//此处将cd的值设置为-(C[i]+D[j]),可以用AB数组中的数与cd直接相加,便于判断二者之和是否为0
res+=upper_bound(AB,AB+n*n,cd)-lower_bound(AB,AB+n*n,cd);
/*upper_bound()与lower_bound()函数的用法参见 https://blog.csdn.net/jadeyansir/article/details/77015626
找到AB数组中第一个比cd大的数的位置pos1,减去AB数组中第一个比cd小的数的位置pos2,如果pos1-pos2=1,则说明
在AB数组中,处在pos1和pos2之间的数就是 cd ,详细参考下图,如当cd=-72时,pos1=9,pos2=8,符合条件,res加1;
*/
}
}
printf("%lld\n",res);
}
return ;
}

二分搜索-poj2785

上一篇:/bin/bash^M: bad interpreter: No such file or directory


下一篇:Java 文档注释