D - Pair of Topics

思路：

这个题需要一点思路，ai+aj>bi+bj可以转换成ai-bi+aj-bj>0，也就是c[i]=a[i]-b[i]，只需要找c[i]+c[j]大于0

一开始的想法是枚举i和j，但是很显然会超时

a和b数组内部的顺序不会影响正确答案个数，所以可以排序

从两头缩进，如果a[r]加上比较小的a[l]大于0，那么就有l-r种方法，因为比a[l]大的数加上a[r]也会大于0，这样就能保证方法没有遗漏

当a[l]+a[r]不大于0的时候，说明a[l]太小了，l向右移来找一个更大的a[l]

代码：

#include<iostream>

#include<algorithm>

#include<string>

using namespace std;

long long a[200005], b[200005], c[200005];

int main(){

    long long n, sum = 0;

    scanf("%lld", &n);

    for (int i = 0; i < n; i++)

        scanf("%lld", &a[i]);

    for (int i = 0; i < n; i++)

        scanf("%lld", &b[i]);

    for (int i = 0; i < n; i++)

        c[i] = a[i] - b[i];

    sort(c, c + n);

    int flag, cnt;

    flag = 0; cnt = n - 1;

    while (1){

        if (flag == cnt)

            break;

        if (c[flag] + c[cnt]>0){

            sum += (cnt-flag);

            cnt--;

        }

        else{

            flag++;

        }

    }

    printf("%lld", sum);

    return 0;

}

巴特西

D - Pair of Topics

D - Pair of Topics

最新文章

热门文章