誰能告訴我爲什麼這會超過2秒的時間限制？（短代碼）

Question

我一直在爲它掙扎2天。請問誰能告訴我爲什麼超過時間限制，當我用作輸入20000以及0和40000之後的數字？我試圖讓變量類型儘可能大，但這似乎也沒有幫助。

#include <bits/stdc++.h> 

using namespace std; 

int main() 
{ 
    /*freopen("file.in", "r", stdin); 
    freopen("file.out", "w" , stdout);*/ 
    long long int aux,i, n, k, j, total = 0; 
    cin >> n >> k; 
    long long int a[n], b[n], order[n]; 
    signed long long int profit[n]; 
    for(i = 0; i < n; i++) 
     cin >> a[i]; 
    for(i = 0; i < n; i++) 
     cin >> b[i]; 
    for(i = 0; i < n; i++) 
     profit[i] = a[i] - b[i]; 
    for(i = 0; i < n; i++) 
     order[i] = i; 
    for(i = 0; i < n; i++) 
     for(j = i + 1; j < n; j++) 
      if(profit[order[i]] > profit[order[j]]) 
      { 
       aux = order[i]; 
       order[i] = order[j]; 
       order[j] = aux; 
      } 
    if(k > 0) 
     for(i = 0; i < k; i++) 
     { 
      total += a[order[i]]; 
     } 

    for(i = k; i < n; i++) 
    { 
     if(profit[order[i]] < 0) 
      total += a[order[i]]; 
     else 
      total += b[order[i]]; 
    } 
    cout << total; 

    return 0; 
} 

Answer 1

你的代碼的複雜度是O（n^2），這對於N = 20000來說太多了。降低複雜性，用Qsort替換你的氣泡排序。試用std::sort自定義比較功能。