算术溢出

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变量是相当小的，这有可能在那里你四溢的变量。