POJ2785 4 Values whose Sum is 0 (二分)

标签:class   序列   std   com   sort   poj   mamicode   const   ios   

技术图片

  • 题意:给你四组长度为\(n\)序列,从每个序列中选一个数出来,使得四个数字之和等于\(0\),问由多少种组成情况(仅于元素的所在位置有关).

  • 题解:\(n\)最大可以取4000,直接暴力肯定是不行的,我们可以先对后两个数组\(c\)\(d\),枚举他们每个元素的和,用一个新数组\(CD\)记录,然后再去枚举\(a\)\(b\)的和,那么我们只要在\(CD\)中二分查找\(a\)\(b\)的和的相反数就好了.

  • 代码:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #define ll long long
    using namespace std;
    const int N=1e7+10;
    
    int n;
    ll a[N],b[N],c[N],d[N];
    ll cd[N];
    ll res;
    
    int main(){
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            scanf("%lld %lld %lld %lld",&a[i],&b[i],&c[i],&d[i]); 
        } 
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                cd[i*n+j]=c[i]+d[j];    
            } 
        }
        sort(cd,cd+n*n); 
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                ll now=-(a[i]+b[j]);
                res+=upper_bound(cd,cd+n*n,now)-lower_bound(cd,cd+n*n,now);
            } 
        }
        printf("%lld\n",res);
        return 0;
    }
    
    

POJ2785 4 Values whose Sum is 0 (二分)

标签:class   序列   std   com   sort   poj   mamicode   const   ios   

原文地址:https://www.cnblogs.com/lr599909928/p/13886599.html

版权声明:完美者 发表于 2020-10-31 1:32:05。
转载请注明:POJ2785 4 Values whose Sum is 0 (二分) | 完美导航

暂无评论

暂无评论...