POJ 2785 4 Values whose Sum is 0

技术文章 10个月前 完美者
1,326 0

标签:复杂度   时间复杂度   lower   复杂   sort   log   who   cin   hose   

折半搜索,\(O(n)\)型枚举,时间复杂度(\(O(n^2logn)\))

const int N=4010;
int a[N],b[N],c[N],d[N];
int ab[N*N];
int n;

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            ab[i*n+j]=a[i]+b[j];

    sort(ab,ab+n*n);

    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            int cd=c[i]+d[j];
            ans+=upper_bound(ab,ab+n*n,-cd)-lower_bound(ab,ab+n*n,-cd);
        }

    cout<<ans<<endl;
    //system("pause");
}

POJ 2785 4 Values whose Sum is 0

标签:复杂度   时间复杂度   lower   复杂   sort   log   who   cin   hose   

原文地址:https://www.cnblogs.com/fxh0707/p/14128115.html

版权声明:完美者 发表于 2020-12-18 12:31:13。
转载请注明:POJ 2785 4 Values whose Sum is 0 | 完美导航

暂无评论

暂无评论...