如何优化代码提升速度并消除嵌套循环？（Codeforces 706B）

问题背景 #

在解决Codeforces 706B题目时，当输入规模达到100000时，代码持续出现Time Limit Exceeded（TLE）错误，需要通过优化消除时间复杂度过高的问题。

最初的嵌套循环实现 #

最初采用嵌套循环统计可购买饮品的店铺数量，代码如下：

#include <iostream>
using namespace std;
int main(){
    int arr[100000];
    int n, x, q, m;
    cin >> n; //售卖饮品的店铺数量
    for (int i = 0; i < n; i++){
        cin >> x; //每家店的饮品价格
        arr[i] = x; //存入数组
    }  

    cin >> q; //天数
    for (int i = 0; i < q; i++){
        cin >> m; //当天可花费的金额
        int count = 0;
        for (int j = 0; j < n; j++){
            if (m >= arr[j]){ //当前金额足够购买该店饮品时，计数器加1
                count++;
            }
        }
        cout << count << '\n'; //输出可购买的店铺数量
    }
}

问题分析：这段代码的时间复杂度为O(q*n)，当n和q均为100000时，总操作次数达到10^10，远超时间限制，必然触发TLE。

第二次错误的排序+upper_bound实现 #

尝试使用排序+upper_bound优化，但仍出现TLE，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int arr[200000];
    int n, x, q, m;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x;
        arr[i] = x;
    }  

    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> m;
        int count = 0;
        //每次查询都排序数组
        sort(arr, arr + n);
        //找到第一个大于m的元素位置
        int upper1 = upper_bound(arr, arr + n, m) - arr;
        cout << upper1 << '\n';
    }
}

问题分析：错误地将sort放在了查询循环内，每次查询都对数组进行排序。排序的时间复杂度为O(n log n)，q次查询的总时间复杂度为O(qn log n)，当n和q为100000时，操作次数依然达到约510^10，远超时间限制。

正确优化方案 #

将排序操作移到查询循环之前，只对数组排序一次，之后每次查询使用upper_bound进行二分查找，时间复杂度降为O(n log n + q log n)，完全符合题目时间要求。

正确代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); //加速输入输出，避免因IO慢导致的TLE

    int arr[100000];
    int n, x, q, m;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x;
        arr[i] = x;
    }  

    //仅排序一次
    sort(arr, arr + n);

    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> m;
        //二分查找第一个大于m的元素位置，位置值即为可购买的店铺数量
        int cnt = upper_bound(arr, arr + n, m) - arr;
        cout << cnt << '\n';
    }
    return 0;
}

额外优化：添加ios::sync_with_stdio(false);和cin.tie(nullptr);关闭C++标准IO与C IO的同步，解绑cin和cout，大幅加速输入输出速度，避免因IO操作缓慢导致的隐性TLE。

内容的提问来源于stack exchange，提问作者Mohamed Darwesh