Pair of Topics CodeForces - 1324D
你有两个长度为n的数列 a 和 b。
现在我们定义,若存在 i 和 j,满足: (i<j) 且 (a[i]+a[j]>b[i]+b[j]),则我们称数对<i,j>为JNU数对
你的目标是统计有多少个这样的数对。
Input
题目含有多组数据,以下为每组数据的格式:
第一行输入n,满足:2 <= n <= 200000;
第二行输入a数列,满足:1 <= a[i] <= 1000000000;
第二行输入b数列,满足:1 <= b[i] <= 1000000000;
Output
一行,输出JNU数对的个数
Sample Input
5
5 9 3 7 3
5 6 5 3 4
4
1 3 2 4
1 3 2 4
Sample Output
7
0
提示:注意本题变量的取值范围所允许的时间复杂度(O(n)或O(logn)),然后考虑在该复杂度下有什么算法~
分析
求:(i<j) 且 (ai+aj > bi+bj) 的 <i,j> 对数,
方法1:枚举 i,j,复杂度 O(n^2),本题超时。
方法2:二分
其中 ai+aj > bi+bj 可以转化为 :ai-bi > -(aj-bj),
用 ci=ai-bi,则问题转化为:ci 中求 i<j 且 (ci > -cj ==> -ci < cj ) 的 <i,j> 对数。
可以先对 c[] 进行排序,再利用 upper_bound 查找 在区间 [i+1, n] 大于(-ci)的位置 p,那么大于 (-ci) 的数量就是 (n-p+1),如果没有大于 (-ci) 的就是 0,恰好 upper_bound 查找无结果会返回 (a+n+1),即 p=n+1,数量为 0。
方法3:双指针
充分利用 c[] 的单调性,结合双指针计算 (ci+cj > 0) 的数量,l=1, r=n,向中靠近,直到 l>=r,每次 (ans += r-l)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10, INF=0x3f3f3f3f;
int n,a[N],b[N],c[N];
LL slove1(){
LL ans=0;
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(a[i]+a[j] > b[i]+b[j]) ans++;
return ans;
}
LL slove2(){ // binSearch - O(nlogn)
LL ans=0;
sort(c+1, c+1+n);
for(int i=1; i<=n; i++){
int p = upper_bound(c+1+i, c+1+n, -c[i]) - c;
ans += (n-p+1);
}
return ans;
}
LL slove3(){// two-points - O(nlogn)
LL ans=0;
sort(c+1, c+1+n);
int l=1, r=n;
while(l < r){
if(c[l] + c[r] > 0) ans += (r-l), r--;
else l++;
}
return ans;
}
int main(){
// freopen("data.in", "r", stdin);
while(~scanf("%d", &n)){
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=n; i++) scanf("%d", &b[i]);
for(int i=1; i<=n; i++) c[i]=a[i]-b[i];
printf("%lld\n", slove3());
}
return 0;
}
标签:ci,1324D,int,Topics,CodeForces,bi,ans,Pair,LL
From: https://www.cnblogs.com/hellohebin/p/16719801.html