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

古城微笑少年丶 2023-07-14 10:41 30阅读 0赞

### 题目： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

### 题意： ###

已知长度为n的a数组&b数组  
问有多少对i，j使（ai+aj>bi+bj）成立。

### 分析： ###

式子可以转化为（(ai-bi)+(aj-bj)>0）,  
使数组c\[k\]=a\[k\]-b\[k\];  
对数组c进行排序

定义指针在c数组两端  
右指针移动一次，总结果增加一次，  
当左右指针相遇，跳出循环得到结果。

Integer一定要用Integer  
不要用int，int会导致程序运行自动装箱操作，导致超时

### AC代码 ###

import java.util.*;
    public class D { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		Integer n = sc.nextInt();
    		Integer a[] = new Integer[n], b[] = new Integer[n], d[] = new Integer[n];
    		for (int i = 0; i < n; i++)
    			a[i] = sc.nextInt();
    		for (int i = 0; i < n; i++)
    			b[i] = sc.nextInt();
    		for (int i = 0; i < n; i++)
    			d[i] = a[i] - b[i];
    		Arrays.sort(d);
    		long ans = 0;
    		int l = 0, r = n - 1;
    		while (l < r)
    			if (d[l] + d[r] > 0) { 
    				ans = ans + r - l;
    				r--;
    			} else
    				l++;
    		System.out.println(ans);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230529/a0817dfa7adb4d6dbcef8128448f1261.png

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #834 (Div. 3) D. Make It Round

[Problem - D - Codeforces][] ![1c21641e1301413ea5db4b38f928ab5a.png][] Code： incl

￡神魔★判官ぃ/ 2024年03月31日 13:51/ 0 赞/ 111 阅读

相关 Codeforces Round #839 (Div. 3) D. Absolute Sorting

[Problem - D - Codeforces][] 题意：给定一个数列，让你选定一个 x ，然后让所有数都变成 abs(a\[i\]-x)，问你 x 取多少可以使该

悠悠/ 2024年03月30日 12:37/ 0 赞/ 113 阅读

相关 Codeforces Round #627 (Div. 3) F. Maximum White Subtree 树形DP 换根

题目链接：[http://codeforces.com/contest/1324/problem/F][http_codeforces.com_contest_1324_pro

太过爱你忘了你带给我的痛/ 2023年07月15日 13:03/ 0 赞/ 48 阅读

相关 Codeforces Round #627 (Div. 3) E. Sleeping Schedule 线性DP

题目链接：[http://codeforces.com/contest/1324/problem/E][http_codeforces.com_contest_1324_pro

墨蓝/ 2023年07月15日 13:02/ 0 赞/ 55 阅读

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

题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

古城微笑少年丶/ 2023年07月14日 10:41/ 0 赞/ 31 阅读

相关 Codeforces Round #667 (Div. 3)（A、B、C、D、E）

Codeforces Round \667 (Div. 3)（A、B、C、D、E） [比赛地址][Link 1] 补题补晚了，估计访问量没了 A：Yet Anoth

àì夳堔傛蜴生んèń/ 2022年12月04日 04:29/ 0 赞/ 192 阅读

相关 Codeforces Round #479 (Div. 3)

D:[Divide by three, multiply by two][Divide by three_ multiply by two] 除了这种做法还可以通过建图

￡神魔★判官ぃ/ 2022年05月24日 20:59/ 0 赞/ 229 阅读

相关 Codeforces Round #506 (Div. 3) D. Concatenated Multiples

题目：[点击打开链接][Link 1] 题意：给你n个数，求任意两个数组合而成能整除k的对数。分析：根据除法的定义暴力就行了，用map或者unordered\_

小鱼儿/ 2022年05月15日 06:35/ 0 赞/ 187 阅读

相关 D. Zero Quantity Maximization（CF： Codeforces Round #544 (Div. 3)）

题目描述： You are given two arrays aa and bb, each contains nn integers. You want to cre

墨蓝/ 2022年03月11日 16:50/ 0 赞/ 222 阅读

相关 Codeforces Round #552 (Div. 3)D、E题解

D. Walking Robot 题意机器人在一维坐标轴上从0走到x，中途可以在有光的地方可以选择给太阳能电池充电，每次移动都要消耗一单位电，蓄电池容量为a，太阳

￡神魔★判官ぃ/ 2022年01月12日 08:19/ 0 赞/ 264 阅读