用於計算條件爲真的實例的代碼

最近，我正在通過this codechef問題來練習即將到來的zoc。用於計算條件爲真的實例的代碼

該問題要求計算給定數字的組合數量，其中總和大於另一個給定數字。

此前我有一個bruteforce算法給出了正確的答案，但花了很多時間，在某些情況下，甚至超過一秒鐘，在codechef中引發了TLE錯誤。

所以我改變了我的整個算法來擺脫TLE錯誤，但現在它只給出第一個測試的正確答案，其餘的產生錯誤的輸出，有人能幫我弄清楚我在做什麼錯誤：

#include <iostream> 
#include <vector> 
int main(){ 
    std::vector<long long> tstCases; 
    std::vector<long long> okset; 
    std::vector<long long> testset; 
    for(int i =0;i<2;i++){ 
     long long cases; 
     std::cin >> cases; 
     tstCases.push_back(cases); 
    } 
    long long n = tstCases.at(0); 
    long long k = tstCases.at(1); 
    for(long long i =0;i<n;i++){ 
     long long cases; 
     std::cin >> cases; 
     if(cases<=k){ 
      if(cases < k/2){ 
       okset.push_back(cases); 
      }else{ 
       testset.push_back(cases); 
      } 
     } 
    } 
    long long l = okset.size(); 
    long long p1 = (l*(l-1))/2; 
    long long p2 = 0; 
    if(l > 0){ 
     for(long long i =0;i<l;i++){ 
      for(long long j =0;j<testset.size();j++){ 
       if(okset.at(i)+testset.at(j) >= k){ 
        break; 
       }else{ 
        p2++; 
       } 
      } 
     } 
    } 
    long long p = p1+p2; 
    std::cout << p << std::endl; 
    return 0; 

}

注：我使用long long因爲這個問題指示我這樣做，我夠懶自己做，所以我用全部更換。對不起。

來源

2016-08-23 Kuntal Majumder

爲什麼你要使用break conditon，可以有更多的值滿足可以存在的條件，因爲你還沒有對'testset'向量進行排序。 – uSeemSurprised

啊，現在我記得，我已經在紙上排序過，但沒有編碼。謝謝 –

嗯仍然代碼未能通過在給定的時間限制內的最後一次測試，結果我得到一個TLE，但我必須改進算法，天哪，以及我可以說我已經學會了一些Asymtotic分析。 –

好吧，它看起來像我沒有排序測試集數組，因此許多項目後，這個break語句。謝謝uSeemSurprised幫助我注意到這一點。

來源

2016-08-23 16:59:27

用於計算條件爲真的實例的代碼

回答

相關問題