4 Values whose Sum is 0 POJ - 2785（二分应用）

题意：输入一个数字n,代表有n行a,b,c,d,求a+b+c+d=0有多少组情况。

思路：先求出前两个数字的所有情况，装在一个数组里面，再去求后两个数字的时候二分查找第一个大于等于这个数的位置和第一个大于这个数的位置相减，得出有多少个答案，累加得出最终答案.

过程： 刚开始写的时候，用的是map把原来的答案存起来，后来发现超时，因为在存数的时候和取数的时候都消耗时间，所以就用容器直接存，二分查找得出答案，结果二分函数又忘了，于是自己尝试着写了一个，就过了。

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;

}

巴特西

4 Values whose Sum is 0 POJ - 2785（二分应用）

最新文章

热门文章