蓝桥杯真题_小蓝和小桥的讨论

小蓝和小桥的讨论

问题描述

小蓝和小桥是一所高中的好朋友，他们正在讨论下一次的课程。这节课需要讨论 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

样例输出

你的代码使用归并排序计数来解决计算 (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)