Codeforces 1324 D-Pair of Topics（思维+二分 || 双指针）

Pair of Topics

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

The next lecture in a high school requires two topics to be discussed. The i-th topic is interesting by ai units for the teacher and by bi units for the students.

The pair of topics i and j (i<j) is called good if ai+aj>bi+bj (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.

Input

The first line of the input contains one integer n (2≤n≤2⋅105) — the number of topics.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is the interestingness of the i-th topic for the teacher.

The third line of the input contains n integers b1,b2,…,bn (1≤bi≤109), where bi is the interestingness of the i-th topic for the students.

Output

Print one integer — the number of good pairs of topic.

Examples

inputCopy

5

4 8 2 6 2

4 5 4 1 3

outputCopy

7

inputCopy

4

1 3 2 4

1 3 2 4

outputCopy

0

题意：

给你两个数组a[i]和b[i]，问有多少对 ( i , j ) 满足i<j 并a[i]+a[j]>b[i]+b[j]。

思路一：二分

可以对式子进行化简，变为a[i]+a[j]-b[i]-b[j]>0，相当于a[i]-b[i]+(b[j]-a[j]) >0 。

可以再开一个新的数组c[i]=a[i]-b[i],那么问题就转变成了：在数组c中寻找一组数，使得其满足i<j 并且 c[i] +c[j]>0

这时候有两种解法：

一是直接两层for循环枚举，复杂度是n^2，显然对于本题，2e5*2e5并不可取。

二是优化第二层for循环，我们可以对c数组升序排序，上述式子可以化成c[j] >-c[i] ， 那么我们可以在第二层for循环的时候直接二分查找第一个大于 -c[i] 的数的位置tmp，那么这个位置及其之后的位置一定符合题意，即 sum+=n-tmp+1;

但是这里要注意c[i] >0 的情况，因为查找的是-c[i] ，所以c[i]也符合查找条件，但是并不符合题意，我们要出去这种情况。

最后需要注意我们每一个逆序对都计算了两遍，需要把结果/2再输出。这样的复杂度就是n*lgn。

最后的最后，要注意在这种思路下，会爆int，所以要用long long 计数。

二分代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
typedef long long ll;
ll n,a[maxn],sum;
int main(){
    cin>>n;
    int x;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i]-=x;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    puts("");
    for(int i=1;i<=n;i++){
        int tmp=upper_bound(a+1,a+1+n,-a[i])-a;
        sum+=n-tmp+1;
    if (a[i]>0) sum--;
     //cout<<i<<" "<<tmp<<" "<<sum<<endl;//检测输出
    }
    cout<<sum/2;
    return 0;
}

思路二：双指针

一般来说，能二分的都能用双指针解决，复杂度基本相同~

双指针代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int n,a[maxn],x,l,r;
ll ans;
int main()
{
  scanf("%d",&n);
  r=n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++) cin>>x,a[i]-=x;
  sort(a+1,a+n+1);
  for(int l=1;l<=n;l++)
  {
    while(a[l]+a[r]>0)r--;///找最后一个满足条件的位置
    ans+=n-max(l,r);//该位置之后的一定满足条件
  }
  printf("%lld",ans);
  return 0;
}

以前在牛客做过一个类似的题，暂时还没找到，先这样叭，这个题再推一下就能解决了qwq 写题解的时候才发现自己推错了。。

还有一种通用的解法，当不具备单调性时可以用树状数组或线段树维护，待补。