Codeforces Round #627 (Div. 3) D - Pair of Topics（双指针）

题意：

有长为n的a，b两序列，问满足a_i+a_j>b_i+b_j(i<j)的i，j对数。

思路：

移项得：(a_i-b_i)+(a_j-b_j)>0，i<j即i!=j，用c序列保存所有a_i-b_i的值，排序，若左右数之和大于0，则右数与二数间的数之和都大于0，计入结果后移动右指针，否则移动左指针。

Tips：

c[i]+c[j]和ans可能会超范围

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(){

    int n;cin>>n;

    ll a[n],b[n];

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

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

    ll c[n];

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

    sort(c,c+n);

    ll l=0,r=n-1,ans=0;

    while(l<r){

        if(c[r]+c[l]>0) ans+=r-l,--r;

        else ++l;

    }

    cout<<ans<<endl;

}

int main(){

    solve();

    return 0;

}

巴特西

Codeforces Round #627 (Div. 3) D - Pair of Topics（双指针）

题意：

思路：

Tips：

最新文章

热门文章