问题描述

威慑纪元 2233 年，人类地球联邦为了突破质子科技封锁，决定在太阳系的黄道平面上建造大量高能粒子对撞机，与普通高能粒子对撞机不同的是，可以将黄道平面抽象为一个二维平面。

一共有 nn 个 αα 高能粒子和 mm 个 ββ 高能粒子，αα 高能粒子的运动轨迹可以被描述为直线 yi=ai×xi+biyi​=ai​×xi​+bi​，ββ 高能粒子的运动轨迹可以被描述为直线 x=cix=ci​。

因为越靠近对撞中心的粒子，其被质子干扰的程度越低，所以为了获得最准确的数据，我们需要选取一个合适的 ββ 粒子的运动轨迹，使得其与 αα 粒子运动轨迹的交点的 yy 值的中位数最大。

输入格式

输入第 11 行包含一个正整数 nn（1≤n≤1051≤n≤105），表示 αα 粒子的数量，保证 nn 为奇数。

第 2∼n+12∼n+1 行每行包含 22 个正整数 ai,biai​,bi​ （−109≤ai,bi≤109−109≤ai​,bi​≤109），分别表示 αα 高能粒子的直线轨迹方程的两个参数。

接下来 11 行包含一个正整数 mm（1≤m≤5×1051≤m≤5×105），表示 ββ 粒子的数量。

再接下来 11 行包含 mm 个整数，表示 ββ 粒子的轨迹方程的参数 c1,c2,...,cmc1​,c2​,...,cm​（1≤ci≤1091≤ci​≤109）。

保证 αα 粒子的运动轨迹两两不同，ββ 粒子的运动轨迹两两不同。

输出格式

输出两个数字，表示选择的 ββ 粒子的下标编号 idid 和最大化的中位数。

下标编号 idid 从 11 开始。

样例输入

5
2 4
-2 1
4 5
-1 3
-2 -4
4
-3 3 2 -1

样例输出

1 2

样例解释

第 11 个 ββ 粒子的运动轨迹与 αα 粒子相交了 55 个点，对应的 yy 值分别为 −2,7,−7,6,2−2,7,−7,6,2，中位数为 22 。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n), b(n);for (int i = 0; i < n; ++i) {cin >> a[i] >> b[i];}int m;cin >> m;vector<pair<int, int>> cs(m); // 存储c值和原始索引for (int i = 0; i < m; ++i) {int c;cin >> c;cs[i] = {c, i + 1}; // 保存原索引（从1开始）}int k = (n + 1) / 2; // 中位数的位置（第k大的数，从1开始）int max_median = INT_MIN;int best_id = -1;vector<int> y(n);for (const auto& c_pair : cs) {int c = c_pair.first;int idx = c_pair.second;// 计算所有y值for (int i = 0; i < n; ++i) {y[i] = a[i] * c + b[i];}// 使用快速选择找到第k大的元素（降序排列后的第k-1个索引）nth_element(y.begin(), y.begin() + k - 1, y.end(), greater<int>());int current_median = y[k - 1];// 更新最大中位数及其对应的idif (current_median > max_median || (current_median == max_median && idx < best_id)) {max_median = current_median;best_id = idx;}}cout << best_id << " " << max_median << endl;return 0;
}

代码结构

1. 头文件与输入优化：

   • 包含必要的头文件，并使用ios::sync_with_stdio(false)和cin.tie(nullptr)来加速输入输出。

2. 输入处理：

   • 读取整数n，表示有n个线性函数。

   • 读取两个数组a和b，每个元素代表线性函数的系数。

   • 读取整数m，表示候选参数c的数量。

   • 读取每个候选参数c，并保存其原始索引（从1开始）。

3. 中位数位置计算：

   • 计算中位数的位置k = (n + 1) / 2，即第k大的元素（从1开始计数）。

4. 遍历候选参数c：

   • 对每个候选参数c，计算所有线性函数在该参数下的值y[i] = a[i] * c + b[i]。

   • 使用nth_element快速选择算法找到y数组中的第k大元素作为当前中位数。

5. 更新最大中位数：

   • 比较当前中位数与历史最大值，若更大或相等但索引更小，则更新最大值及其对应的参数索引。

6. 输出结果：

   • 输出最佳参数的索引和对应的最大中位数。

关键点解释

• 快速选择算法：nth_element函数在O(n)时间内将第k大的元素放置在正确位置，其左侧元素均不小于它，右侧均不大于它，避免了完全排序的时间复杂度O(n log n)。

• 中位数定义：当n为奇数时，取中间值；当n为偶数时，取中间两数的较大者，通过k = (n + 1) / 2实现。

• 索引处理：保存候选参数的原始索引以便输出，并在中位数相同时选择索引较小的参数。

示例说明

假设输入：

3
1 0
2 0
3 0
2
1 2

代码计算每个c对应的y值：

• 当c=1时，y=[1, 2, 3]，中位数为2。

• 当c=2时，y=[2, 4, 6]，中位数为4。