算術溢出

Question

我做了演示codility測試 「NumberOfDiscIntersections」： https://codility.com/programmers/lessons/4

我有：PERF = 100％，正確性87％

所有的測試，但一個都很好：

overflow 
arithmetic overflow tests 

爲什麼我的漫長，不夠？我無法確定哪裏出了問題！

#include <algorithm> 


int solution(const vector<int> &A) 
{ 
    // write your code in C++11 
    vector<long long > vec_max; 
    for(int i = 0; i < A.size(); ++i) 
    { 
     vec_max.push_back(A[i] + i); 
    } 
    std::sort(vec_max.begin(),vec_max.end()); // sort by max 

    int step = 1; 
    int counter = 0; 
    for(int i = A.size() - 1; i > -1; --i) 
    { 
     std::vector<long long>::iterator low; 

     int nb_upper = A.size() - (lower_bound(vec_max.begin(),vec_max.end(), (long long) (i - A[i])) - vec_max.begin()); 
     counter += nb_upper - step; 
     ++step; 
    } 

    if (counter > 10000000) 
    { 
     return -1; 
    } 
    else 
    { 
     return counter; 
    } 
} 

Answer 1

如果A陣列是非常大的，你可能最終將大指數櫃檯int變量。相比於它

counter += nb_upper - step; 

的step變量是相當小的，這有可能在那裏你四溢的變量。