UVa 11124 Troubles for Modern Days Problemsetters

题目描述

给定一个最多包含 $1000000$ 个数字的列表，顺序任意，求该列表按非降序排序后第 $i$ 个元素的值。为了避免输入数据量过大导致 $\text{I/O}$ 成为性能瓶颈，题目要求参赛者根据给定的三种列表命令动态生成数据。

三种列表命令如下：

多个列表命令可以通过 + 连接，生成一个拼接后的完整列表。所有生成的数字均为 $32$ 位有符号整数。输入保证总数字个数在 $1$ 到 $1000000$ 之间，且每行命令数不超过 $32$，行长度不超过 $1000$ 字符。

输入格式

输入包含多个测试用例，每个用例占两行：

• 第一行一个整数 $i$（$1\le i\le$ 列表总长度），表示排序后要找的第 $i$ 个元素（索引从 $1$ 开始）。
• 第二行一个字符串，由若干个列表命令通过 + 连接而成，不含空格。

输入以单独一行 0 结束。

输出格式

对于每个测试用例，输出一行，格式为 Case X: Y，其中 $X$ 为用例编号（从 $1$ 开始），$Y$ 为所求的第 $i$ 个元素。

样例

输入

4
NList(10,-9,6,-4,-3,6,501,7,6,6,-10000)
13
IList(5,0,1)+IList(3,6,0)+IList(5,5,-1)
1
IList(1000000,-90,0)
123456
RList(1000000,-2000000000,2000000000,0)
200000
IList(50001,-25000,1)+RList(500000,-25000,25000,3333333333)+NList(4,0,0,0,0)
0

输出

Case 1: -3
Case 2: 6
Case 3: -90
Case 4: -1735543272
Case 5: -6808

题目分析

本题的核心挑战在于高效地找到大规模无序数组中的第 $i$ 小元素。直接生成所有数字并完整排序的时间复杂度为 $O(n\log n)$，对于 $n=10^6$ 在时限内通常是可行的，但题目特别提示需要“高效的算法”，因此更优的选择是使用快速选择算法。

快速选择（$\text{nth\_element}$）是快速排序的变体，能够在期望线性时间 $O(n)$ 内找到第 $i$ 小的元素，而无需对全数组排序。$\text{C++}$ 标准库中的 std::nth_element 正是这一算法的实现，它部分重排数组，使得第 $i$ 个位置上的元素就是排序后该位置应有的元素，且其左侧元素都不大于它，右侧元素都不小于它。

另一个需要关注的点是数据生成。由于输入以字符串形式给出，且命令数不超过 $32$，总长度不超过 $1000$ 字符，我们可以直接解析每个命令并实时生成数字存入数组。解析时需注意：

• 命令名（NList、IList、RList）和参数之间没有空格；
• 参数用逗号分隔；
• 生成随机数时必须使用 $64$ 位整数（如 long long），防止乘法溢出，同时取模时范围 h – l + 1 可能超过 $32$ 位有符号范围，也需用 $64$ 位处理。

解题思路

步骤一：解析输入命令

对于每个测试用例，读入索引 $i$ 和一行命令字符串。由于命令间用 + 分隔，我们按 + 分割得到每个独立的命令子串。

对每个命令子串：

• 找到左括号 ( 和右括号 ) 的位置；
• 提取括号内的参数部分；
• 将参数中的逗号 , 替换为空格，方便使用 stringstream 读取；
• 根据命令前缀（NList、IList、RList）分别处理。

步骤二：生成数字

• $\text{NList}$：第一个参数为 $n$，随后读取 $n$ 个整数，依次存入数组。
• $\text{IList}$：读取 $n$、$s$、$i$，循环 $n$ 次，每次计算 $s+k\cdot i$ 并存入数组。注意 $k$ 可能很大（最多 $10^6$），但乘积仍可用 $64$ 位安全计算。
• $\text{RList}$：读取 $n$、$l$、$h$、$s$。种子 $s$ 是 $32$ 位无符号整数，但输入可能以十进制给出，应读入为 unsigned long long 再截断为 unsigned int。每次迭代：
  • seed = (seed * 17 + 11) & 0xFFFFFFFFULL；
  • 生成值 l + (seed % (h – l + 1))，由于 h – l + 1 可能超过 int 范围，需用 long long 计算。

步骤三：查找第 $i$ 小元素

将所有生成的数字存入 vector<int> 后，调用 nth_element(nums.begin(), nums.begin() + i – 1, nums.end())，此时 nums[i-1] 即为答案。该函数的时间复杂度为线性期望。

复杂度分析

• 时间复杂度：解析和生成数字 $O(n)$，快速选择 $O(n)$ 期望，总复杂度 $O(n)$。
• 空间复杂度：存储所有数字 $O(n)$，$n\le 10^6$，内存可接受。

代码实现

// Troubles for Modern Days Problemsetters
// UVa ID: 11124
// Verdict: Accepted
// Submission Date: 2026-06-21
// UVa Run Time: 0.100s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

// 解析一行命令，生成所有数字并追加到 nums 中
void parseAndGenerate(const string& line, vector<int>& nums) {
size_t pos = 0;
while (pos < line.size()) {
size_t plus = line.find('+', pos); // 查找命令分隔符
string cmd = line.substr(pos, plus – pos); // 提取单个命令
size_t lp = cmd.find('('), rp = cmd.find(')', lp);
string args = cmd.substr(lp + 1, rp – lp – 1); // 括号内的参数列表
for (char& c : args) if (c == ',') c = ' '; // 逗号转空格便于流读取
stringstream ss(args);

if (cmd.find("NList") == 0) {
int n; ss >> n;
for (int k = 0; k < n; ++k) { int val; ss >> val; nums.push_back(val); }
} else if (cmd.find("IList") == 0) {
int n; long long s, inc; ss >> n >> s >> inc;
for (int k = 0; k < n; ++k) nums.push_back((int)(s + inc * k));
} else if (cmd.find("RList") == 0) {
int n; long long l, h; unsigned long long seed;
ss >> n >> l >> h >> seed;
unsigned int seed32 = (unsigned int)(seed & 0xFFFFFFFFULL);
long long range = h – l + 1; // 可能大于 2^31，用 long long
for (int k = 0; k < n; ++k) {
seed32 = (unsigned int)((seed32 * 17ULL + 11ULL) & 0xFFFFFFFFULL);
nums.push_back((int)(l + (seed32 % range)));
}
}
pos = (plus == string::npos) ? line.size() : plus + 1;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int i, caseNo = 1;
string line;
while (cin >> i) {
if (i == 0) break;
getline(cin, line); // 消耗第一行末尾的换行符
getline(cin, line); // 读取实际的命令行
vector<int> nums;
nums.reserve(1000000);
parseAndGenerate(line, nums);
nth_element(nums.begin(), nums.begin() + i – 1, nums.end());
cout << "Case " << caseNo++ << ": " << nums[i – 1] << "\\n";
}
return 0;
}

总结

本题巧妙地将“大输入生成”与“选择算法”结合起来，考察了两个关键能力：

此外，本题也提醒我们，在竞赛环境中，合理的算法选择（而非盲目排序）往往能显著提升程序性能，而 $\text{C++}$ 标准库中的高效算法（如 nth_element）是实现这一目标的利器。