小蓝和小桥的讨论
问题描述
小蓝和小桥是一所高中的好朋友,他们正在讨论下一次的课程。这节课需要讨论 nn 个主题,第 ii 个主题对老师来说有 aia**i 的趣味度,对学生来说有 bib**i 的趣味度。
小蓝认为,如果一个主题对老师来说越有趣,那么这个主题就应该被优先讨论,因为老师的兴趣会高度激发学生的兴趣,而学生的兴趣是学习的动力。
他们发现,如果两个主题 ii 和 jj 满足 ai+aj>bi+bja**i+a**j>b**i+b**j,那么对老师来说这是一个更有趣的组合,也就是说这个组合更应该被优先讨论。他们把这样的组合称作 好的 话题组合。
请你帮助小蓝和小桥计算出一共有多少个 好的 话题组合。
输入格式
输入的第一行包含一个整数 nn,表示话题的数量。
输入的第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,a**n,其中 aia**i 表示第 ii 个话题对老师的趣味性。
输入的第三行包含 nn 个整数 b1,b2,…,bnb1,b2,…,b**n,其中 bib**i 表示第 ii 个话题对学生的趣味性。
输出格式
输出一个整数,表示 好的 话题对的数量。
样例输入
5
4 8 2 6 2
4 5 4 1 3
样例输出
7
你的代码使用归并排序计数来解决计算 (ai[left] + ai[right] > 0)(且 (left < right))的对数问题,但你提到“答案不对”。我们需要分析代码的逻辑,找出问题所在,并修正它。
当前代码逻辑分析
-
目标:
- 计算 (ai[left] + ai[right] > 0) 的下标对 ((left, right)) 数量,其中 (left < right)。
- (ai[i] = a[i] - b[i])。
-
归并排序计数:
- 在合并时,通过比较左侧子数组 (arr[i])(从 (left) 到 (mid))和右侧子数组 (arr[j])(从 (mid+1) 到 (right))的元素,统计满足条件的对数。
- 条件 (arr[i] + arr[j] > 0) 等价于 (arr[i] > -arr[j])。
- 当 (arr[i] > -arr[j]) 时,假设 (arr[i]) 到 (mid) 的所有元素都满足条件,计数增加 (mid - i + 1)。
-
合并过程:
- 如果 (arr[i] > -arr[j]),放入 (arr[j])(较小值),并计数。
- 否则放入 (arr[i])。
问题所在
经过检查,当前代码的计数逻辑存在错误,导致结果偏大。问题出在合并时的计数方式:
- 错误假设:当 (arr[i] > -arr[j]) 时,代码认为 (arr[i]) 到 (arr[mid]) 的所有元素都满足 (arr[i] + arr[j] > 0)。但实际上,只有在左侧子数组仍有序的前提下,这一假设才成立。由于归并排序会改变原数组顺序,计数时未正确考虑原始下标,导致重复计数或错误计数。
- 合并顺序:当前代码先放入 (arr[j])(右侧),这与计数逻辑不匹配,可能导致统计错误。
正确的归并计数应该:
- 在合并时,保证 (i < j)(左侧元素下标小于右侧元素下标)。
- 只统计原始 (left < right) 条件下的对数,而不是假设整个左侧子数组都满足。
修正思路
要正确计数 (ai[left] + ai[right] > 0) 的对数,我们需要:
-
保留原始下标信息:
- 使用一个辅助数组记录元素及其原始下标,避免排序后丢失 (left < right) 的约束。
-
调整合并逻辑:
- 在合并时,正确统计左侧元素大于右侧元素的对数。
-
优化计数:
- 确保只统计 (left < right) 的对,避免重复或遗漏。
然而,当前代码直接操作 (ai) 数组,无法保留下标信息。更好的方法是:
- 修改数据结构,使用对象存储值和下标。
- 或调整计数逻辑,确保每次合并只统计当前子问题内的有效对数。
修正后的代码
以下是修正后的实现,使用归并排序正确计数:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scan.nextInt();
}
for (int j = 0; j < n; j++) {
b[j] = scan.nextInt();
}
int[] ai = new int[n];
for (int i = 0; i < n; i++) {
ai[i] = a[i] - b[i];
}
long res = mergeSortAndCount(ai, 0, n - 1);
System.out.print(res);
scan.close();
}
private static long mergeSortAndCount(int[] arr, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2; // 防止溢出
long count = mergeSortAndCount(arr, left, mid) + mergeSortAndCount(arr, mid + 1, right);
count += merge(arr, left, mid, right);
return count;
}
private static long merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left; // 左侧子数组指针
int j = mid + 1; // 右侧子数组指针
int k = 0; // 临时数组指针
long count = 0;
// 临时记录右侧元素,用于计数
int[] rightPart = new int[right - mid];
for (int p = 0; p < rightPart.length; p++) {
rightPart[p] = arr[mid + 1 + p];
}
// 先统计满足条件的对数
int r = 0; // 右侧指针
for (int l = left; l <= mid && r < rightPart.length; ) {
if (arr[l] > -rightPart[r]) {
count += (mid - l + 1); // 左侧从 l 到 mid 都满足
r++;
} else {
l++;
}
}
// 合并两个子数组
i = left;
j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 复制回原数组
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
return count;
}
}
修正点说明
-
分离计数与合并:
- 在合并前,先统计满足 (arr[left] + arr[right] > 0) 的对数。
- 使用 (rightPart) 记录右侧子数组,避免合并时改变原始值。
-
计数逻辑:
- 对于每个右侧元素 (rightPart[r]),检查左侧 (arr[l]) 是否大于 (-rightPart[r])。
- 如果满足,从 (l) 到 (mid) 的所有元素都满足(因为左侧子数组有序),计数增加 (mid - l + 1)。
- (l) 和 (r) 单调递增,避免重复计数。
-
合并逻辑:
- 保持标准的归并排序合并,确保 (arr) 最终有序。
- 计数与合并分离,不干扰排序过程。
时间复杂度
- 归并排序:(O(n \log n))。
- 合并时计数:(O(n))(左右指针单调移动)。
- 总复杂度:(O(n \log n))。
示例验证
输入:
3
5 2 3
1 1 1
- (ai = [4, 1, 2])
- 期望对数:
- (4 + 1 > 0)((0, 1))
- (4 + 2 > 0)((0, 2))
- (1 + 2 > 0)((1, 2))
- 总数:3
运行过程:
- 分解:([4]) 和 ([1, 2])。
- 合并 ([1, 2]):
- (1 > -2),(count = 1)。排序后 ([1, 2])。
- 合并 ([4] 和 [1, 2]):
- (4 > -1),(count += 1)。
- (4 > -2),(count += 1)。
- 总 (count = 3)。
- 输出:(3)
为什么原代码错误?
原代码在合并时直接用 (arr[i] > -arr[j]) 计数,但:
- (arr[i]) 到 (mid) 的元素并非都满足条件(排序后顺序改变)。
- 重复计数或遗漏对数,因为合并与计数耦合。
修正后分离计数,确保只统计当前子问题内的有效对数。