POJ2785 4 Values whose Sum is 0

这题网上的解法也是骚不死他

https://blog.csdn.net/Since_natural_ran/article/details/53908637

这里我说几个注意点：

（1）

1处无论从多少开始作为初始下标都可以，但是S数组必须是0开始，原因是：

upper_bound和lower_bound函数的返回值的下标和数组是一致的，意思是如果是数组第一个位置满足lower_bound( )的值，那么僵返回0而不是1 ！！！

（2）

这里不能用A[ ]来代替S数组（即将A[ ]定义为MAXN*MAXN）是不行的，因为A会边赋值边覆盖原来的值，会傲世后面的结果全部错误。

（3）

类似八皇后一样的写法，将二维数组展开成一维，用每个位置坐标来表示，则i , j 必须以0开始，即数组在输入数据时就应该以0开始，不能是1.

这里是i=pos/N,j=pos%N；

 

代码：

//C
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define MAXN 4010

int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int S[MAXN*MAXN];

int main()
{
    int i,j;
    int N;
    int cnt;
    LL ans;
    LL temp;

    while(scanf("%d",&N)!=EOF)
    {
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        memset(D,0,sizeof(D));
        for(i=1;i<=N;i++)
            scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
        cnt=0;
        memset(S,0,sizeof(S));
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                S[cnt++]=A[i]+B[j];
        sort(S,S+N*N);
        ans=0;
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=N;j++)
            {
                temp=-(C[i]+D[j]);
                ans+=upper_bound(S,S+N*N,temp)-lower_bound(S,S+N*N,temp);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}