c++ - 检测循环并加快求和速度

Question

假设给定一个正整数数组，可能是一个非常大的数组，并且给定另一个正整数，我们称它为 k，另一个正整数，我们将其称为 n。

我们将整数相加，同时总和不超过 k，然后从停止的地方重复这个过程(如果我们到达数组的末尾，我们回到第一个)，然后我们继续这个过程.

例如，如果数组是

a[5]={1, 3, 5, 7, 4}

和k,n都是

k=9, n=6

那么我们要经历的6个过程就是

 (1, 3, 5), (7), (4, 1, 3), (5), (7), (4, 1, 3)

总和为 9+7+8+5+7+8 = 44并且以下代码就足够了(realsum 将是总和)

     int g=0;
     int realsum=0;
     while(g < n){
                sum=0;
                while(sum + a[g]<= k){
                sum=sum+a[g];
                pointer=pointer+1;
                if(pointer >=5){
                    pointer=pointer%5; 
                }
               }
               realsum=realsum+sum;
            g++;

        }

5可以换成数组的大小。

无论如何，如果 n 真的很大，我们可以利用存在循环的事实(7), (4, 1, 3), (5), 这将一遍又一遍地重复，这确实会使总和计算更快。我想知道是否有一种好的方法可以检测数组中的此类循环并将其应用于 C++ 中的这个示例。任何帮助将不胜感激。

Answer 1

您可以维护一个数组，该数组存储任意索引处的总和以及数组中给定 k 值的序列的下一个索引。首先检查索引是否有计算值，如果没有计算并存储它。如果已经计算出总和，则使用它并跳转到数组中定义的下一个索引。像这样:

int a[5]={1, 3, 5, 7, 4};
std::pair<int, int> sums[5];
memset(sums, 0, sizeof(sums));
int g=0, pointer=0, n=6, k=9;
int realsum=0;
while(g<n)
{
  int sum=sums[pointer].first;
  if(!sum)
  {
    int ref_pointer=pointer;
    while(sum+a[pointer]<=k)
    {
      sum+=a[pointer];
      if(++pointer==5)
        pointer=0;
    }
    sums[ref_pointer].first=sum;
    sums[ref_pointer].second=pointer;
  }
  else
    pointer=sums[pointer].second;
  realsum+=sum;
  g++;
}