4 Values whose Sum is 0 POJ – 2785

The meaning of the question: Enter a number n, which means there are n rows of a, b, c, d, and find how many groups of a+b+c+d=0 are there.

Idea: First find all the cases of the first two numbers, put them in an [array] , and then when you go to find the last two numbers, binary search for the first position greater than or equal to this number and subtract the first position greater than this number , get how many answers there are, and add up to get the final answer.

Process:  When I first wrote it, I used a map to store the original answer. Later, it was found that it was timed out. Because it took time to store and fetch the number, I used the container to store it directly, and [binary search] was used to get the answer. , as a result, the dichotomous function was forgotten again, so I tried to write one myself, and it was over.

lower_bound(v.begin(),v.edn(),x)-v.begin;

upper_bound(v.begin(),v.end(),x)-v.begin;

#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int a[4005],b[4005],c[4005],d[4005],v[16000025];
bool comp(int a,int b)
{
    return a<b;
}
int yao(int v[],int len,int t)
{
    int l=0,r=len,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(t<v[mid])
            r=mid;
        else
            l=mid+1;
    }
    return r;
}
int main()
{
    int n;
    scanf("%d",&n);
    int w=0;
    for(int i=1; i<=n; i++)
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            v[w++]=a[i]+b[j];
    sort(v,v+w,comp);
    int k,kk,t1,t;
    long long ans=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            t=c[i]+d[j];
            t=t*-1;
            k=lower_bound(v,v+w,t)-v;
            kk=yao(v,w,t);
            ans+=(kk-k);
        }
    printf("%lld\n",ans);
    return 0;
}

Leave a Comment

Your email address will not be published. Required fields are marked *