c++ - Codility 测试中的算术溢出

Question

我做了 codility 演示测试“NumberOfDiscIntersections”: https://codility.com/programmers/lessons/4

我有:性能 = 100% 和正确性 87%

除了一个测试之外的所有测试都很好:

overflow 
arithmetic overflow tests

为什么我的 long long, 还不够？我不知道出了什么问题!

#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 变量添加大索引。 step 变量与其相比非常小

counter += nb_upper - step;

这很可能是您溢出变量的地方。