标签: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
暂无评论...