c++ 如何优化这段代码以提高速度并摆脱嵌套循环?[closed]

blmhpbnm  于 2022-11-27  发布在  其他
关注(0)|答案(1)|浏览(599)

**已关闭。**此问题为not reproducible or was caused by typos。目前不接受答案。

这个问题是由一个打字错误或一个无法再重现的问题引起的。虽然类似的问题在这里可能是on-topic,但这个问题的解决方式不太可能帮助未来的读者。
昨天关门了。
Improve this question
我试图解决This problem,但我总是得到超过时间限制,当输入是100000。我需要优化嵌套循环不知何故。

#include <iostream>
using namespace std;
int main(){
    int arr[100000];
    int n, x, q, m;
    cin >> n; //number of shops that sell the drink
    for (int i = 0; i < n; i++){
        cin >> x; //prices of each drink in the shop
        arr[i] = x; //add it to the array
    }  
 
    cin >> q; //number of days
    for (int i = 0; i < q; i++){
        cin >> m; // money the person will be able to spend on each day
        int count = 0;
        for (int j = 0; j < n; j++){
            if (m >= arr[j]){ //if the amount of money is more or equal
            // to the price of bottle, increase counter
           // (number of shop we can buy from)
                count++;
            }
        }
        cout << count << '\n'; //the number of shops the person can buy drinks in with his money
    }
}

我甚至尝试了另一种方法,使用sort和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 the array
        sort(arr, arr + n);
        //find the upper bound
        int upper1 = upper_bound(arr, arr + n, m) - arr;
        cout << upper1 << '\n';
    }
}

链接到我提交后的第一个解决方案here
链接到我的第二个解决方案后提交here

6mzjoqzu

6mzjoqzu1#

实际上,在进入循环之前,通过对arr只排序一次,可以优化第二个解决方案。

相关问题