I was trying to solve This problem, but I keep getting Time limit exceeded, when the input is 100000. I need to optimize the nested loop somehow.

#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
    }
}

I even tried another approach with sort and upper bound but still 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';
    }
}

link to my FIRST solution after submission here

link to my SECOND solution after submission here

CodePudding user response：

It actually appears that your second solution CAN be optimized, by sorting your arr only once, before going into a loop.