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

57 阅读 0 评论 38 点赞

我是靠谱客的博主调皮季节，最近开发中收集的这篇文章主要介绍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;
}