程序仅35%通过其余为运行时错误，求数组第k项问题优化方案

Hey there! Let's figure out why your code is hitting runtime errors and fix it up.

问题分析 #

Your current approach tries to build the entire array by pushing every single element into the vector, then sorting it. But here's the problem: when the total number of elements (sum of all a_i) gets really big—like if you have 10^5 pairs each with a_i=10^5, that's 10^10 elements total—your vector can't possibly hold that much data. You'll run out of memory instantly, which is why you're seeing runtime errors. Plus, sorting such a huge array would be way too slow, even if memory wasn't an issue.

优化思路 #

Instead of building the actual array, we can work smarter by leveraging the pairs directly:

• First, sort all the (a_i, b_i) pairs by the value b_i (since we need the final array sorted in non-decreasing order).
• Then, iterate through the sorted pairs, keeping a running total of how many elements we've accounted for. As soon as this running total is greater than or equal to k, the corresponding b_i is exactly the k-th element we're looking for.

This approach uses O(n) space (just storing the n pairs) and O(n log n) time (for sorting the pairs), which is perfect for the constraints given (n ≤ 10^5).

修正后的代码 #

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入，处理大量数据时很有用

    ull n, k;
    cin >> n;

    vector<pair<ull, ull>> pairs;
    pairs.reserve(n); // 预分配空间，避免多次内存重分配

    for (ull i = 0; i < n; ++i) {
        ull a, b;
        cin >> a >> b;
        pairs.emplace_back(b, a); // 存储(b_i, a_i)，方便按b_i排序
    }

    sort(pairs.begin(), pairs.end());

    cin >> k;
    ull count = 0;
    for (const auto& p : pairs) {
        count += p.second;
        if (count >= k) {
            cout << p.first << '\n';
            return 0;
        }
    }

    // 题目保证k有效，所以不会执行到这里
    return 0;
}

代码关键点说明 #

• 我们将 pair 存储为 (b_i, a_i)，这样排序时直接按元素值 b_i 升序排列，符合最终数组的顺序。
• ios::sync_with_stdio(false); 和 cin.tie(nullptr); 用于加速输入，当处理1e5条输入时，这能显著减少输入耗时。
• 使用 reserve(n) 预分配vector的空间，避免插入元素时频繁的内存扩容操作，提升效率。
• 遍历排序后的pair，累加元素个数，一旦累计数量达到或超过k，当前的 b_i 就是我们要找的第k个元素。

内容的提问来源于stack exchange，提问作者walkthrough TV