PKU 2785 - 4 Values whose Sum is 0 (二分 + 思维)

题意

找出四元组a+b+c+d=0的个数。

思路

枚举a+b,找c+d。

用map竟然TLE了,明明和手动二分一样的复杂度。

代码

vector<int> s1, s2;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int main()
{
    //ROP;
    int n;
    while (~scanf("%d", &n))
    {
        s1.clear(); s2.clear();
        for (int i = 0; i < n; i++) scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                s1.PB(a[i]+b[j]);
                s2.PB(-c[i]-d[j]);
            }
        int cnt = 0;
        sort(s2.begin(), s2.end());
        for (int i = 0; i < SZ(s1); i++)
        {
            int x = lower_bound(s2.begin(), s2.end(), s1[i]) - s2.begin();
            int y = upper_bound(s2.begin(), s2.end(), s1[i]) - s2.begin();
            cnt += y-x;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

Powered by Jekyll and Theme by solid