竞赛题City Plan：O(n)解法仍超时（TLE）的问题排查求助

• 每个测试点时间限制：2秒
• 内存限制：256MB
• 输入：标准输入
• 输出：标准输出

问题描述 #

某城市有n栋房子沿直路建造，第i栋房子位于整数点xi（0≤xi≤1e9，所有xi互不相同）。需为每栋房子i计算到其他房子的最远距离di，即di=max₁≤k≤n(|xi−xk|)。现丢失了xi列表，需根据di数组构造符合要求的xi数组。

输入格式 #

第一行是测试用例数t（1≤t≤1e4），每个测试用例第一行是n（2≤n≤2e5），第二行是n个整数d₁~dₙ（1≤di≤1e7），输入保证di数组合法，所有测试用例的n总和不超过2e5。

输出格式 #

输出n个互不相同的整数xi（0≤xi≤1e9），满足对应的di数组，顺序需对应。

我的问题 #

我编写了时间复杂度为O(n)的C++解法，但提交后仍出现超时（TLE）错误，不清楚问题所在，附上我的代码：

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, maximum = -1;
    cin >> n;
    vector<int> a(n, 0);

    for (int i=0; i < n; ++i) {
        cin >> a[i];
        maximum = max(a[i], maximum);
    }

    vector<bool> mark(maximum + 1, 0);
    for (int i=0; i < n; ++i) {
        if (mark[maximum - a[i]])
            cout << 0 + a[i] << " ";
        else {
            cout << maximum - a[i] << " ";
            mark[maximum - a[i]] = 1;
        }
    }
    cout << '\n';
    return;
}   
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve(); 
    return 0;
}

请求帮助排查超时原因。

超时原因分析 #

你的代码超时的核心问题在于**vector<bool> mark(maximum + 1, 0)**这一行：

• 题目中di的最大值可达1e7，当某个测试用例的maximum为1e7时，你会创建一个大小为1e7+1的bool数组。初始化这个数组的时间复杂度是O(1e7)，远超过单个测试用例允许的O(n)操作量（n最大2e5），直接拖慢程序运行速度。
• 若存在多个包含大maximum的测试用例，反复分配、释放大内存会带来额外的内存开销，进一步加剧超时问题。

优化方案 #

用哈希表（如unordered_set<int>）替代数组标记，这样空间和时间开销仅与n相关，不受di最大值影响：

修改后的代码示例：

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, maximum = -1;
    cin >> n;
    vector<int> a(n, 0);

    for (int i=0; i < n; ++i) {
        cin >> a[i];
        maximum = max(a[i], maximum);
    }

    unordered_set<int> used;
    for (int i=0; i < n; ++i) {
        int val = maximum - a[i];
        if (used.count(val)) {
            cout << a[i] << " ";
        } else {
            cout << val << " ";
            used.insert(val);
        }
    }
    cout << '\n';
}   
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve(); 
    return 0;
}

额外优化细节：

• 原代码中0 + a[i]可直接写为a[i]，移除无意义运算。
• 若unordered_set出现哈希冲突，可改用set，不过unordered_set平均时间复杂度为O(1)，更适配本题需求。

内容的提问来源于stack exchange，提问作者Alpha々 Reaper