首页 > 其他分享 >Pair of Topics CodeForces - 1324D

Pair of Topics CodeForces - 1324D

时间:2022-09-22 22:14:53浏览次数:56  
标签:ci 1324D int Topics CodeForces bi ans Pair LL

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

相关文章

  • Codeforces Round #298 (Div. 2) - D. Handshakes
    贪心+构造题意有\(n(1<=n<=2*10^5)\)个人,每分钟有一个人进入房间,房间里任意3个人可以组队开始工作并一直持续下去,且只要房间里至少有3个人,他们就可以在任意时间......
  • Codeforces Round #814
    难得遇上一把CF,结果unr了。AMainakandArray显然最优策略只有三种:选一个\(i\in[1,n-1]\)的\(a_i\)作为\(a_1\);选一个\(i\in[2,n]\)的\(a_i\)作为\(a......
  • Polycarp Writes a String from Memory CodeForces - 1702B
    PolycarpWritesaStringfromMemoryCodeForces-1702B给定大小为n的字符串,至多每3种不同的字母分为一组,最少将字符串分为多少组?Input第一行输入数据包含一个整......
  • Jzzhu and Children CodeForces - 450A
    JzzhuandChildrenCodeForces-450A有n个孩子在老师的学校上学。老师决定给这些孩子一些苹果。让我们将所有孩子编号为1到n。第i个孩子想要获得至少ai的苹果......
  • CodeForces-189A Cut Ribbon-必须装满的背包
    题意:给定n,s.t. a1*x1+a2*x2+a3*x3=n(1)max:x1+x2+x3对比完全背包,(1)式取等号而不是<=这个差别影响了我们的结果比如:n=7,a1=a2=5,a3=2如果按照完全背包的转移:则在dp[7......
  • Codeforces Round #813 (Div. 2) - D. Empty Graph
    构造Problem-D-Codeforces题意给\(n(1<=n<=10^5)\)个点,与权值\(a_i\),这\(n\)个点组成一个完全图,\(a_l\)与\(a_r\)连的边的权值为\(min(a_l,a_{l+1}...a_{r......
  • Codeforces Round #821 (Div. 2) D E
    E首先发现无论何时,每个位置上至多只会有一个球。原因:每个时刻每个球都会移动,所以移动到某个点的时间一定,自然出生时间也一定,显然不可能会有2个点出生时间相同。既然如......
  • Educational Codeforces Round 119 E
    E.ReplacetheNumbers开始想到了一个二分的做法好像是O(nlog)的后来才想了一下可以在两个数组之间反复横跳那我是不是像记忆化搜索一样记录一个路径即可我们记录f[i]......
  • Codeforces Round #818 (Div. 2) - D. Madoka and The Corruption Scheme
    思维+组合数学Problem-D-Codeforces题意有\(2^n\)个人进行锦标赛,编号1~\(2^n\),每一场输的人失去比赛资格,赢的人继续。Madoka可以选择他们进行的顺序,以及决定哪一......
  • Codeforces 821 Div2
    T1:大小为n的数组,最多进行k次操作:下标模k意义下相等则可进行交换。求操作后连续k个元素的最大值固定最大值的k个连续因素小标为[0,k),现在只需使得它为最大即可,将可交换位......