我有一个级数“a”，其中给出了前两个数字(a1 和 a2)，每个下一个数字是大于前一个数字的子数组的最小总和。

例如，如果我有 a1 = 2 和 a2 = 3，那么进度将是

2, 3, 5(=2+3), 8(=3+5), 10(=2+3+5), 13(=​​5+8), 16(=3+5+8) , 18(=2+3+5+8=8+10), 23(=5+8+10=10+13), 26(=3+5+8+10), 28(=2+3+5 +8+10), 29(=13+16)...

我需要找到这个级数中的第 N 个数字。 (限时0.7秒)

(a1小于a2，a2小于1000，N小于100000)

我尝试了优先级队列、集合、映射、https://www.geeksforgeeks.org/find-subarray-with-given-sum/和其他一些东西。

我虽然优先队列可以工作，但它超过了内存限制(256 MB)，所以我几乎没有希望了。

这是目前表现最好的。

int main(){
  int a1, a2, n;
  cin>>a1>>a2>>n;

  priority_queue< int,vector<int>,greater<int> > pq;
  pq.push(a1+a2);

  int a[n+1];//contains sum of the progression
  a[0]=0;
  a[1]=a1;
  a[2]=a1+a2;

  for(int i=3;i<=n;i++){

    while(pq.top()<=a[i-1]-a[i-2])
      pq.pop();

    a[i]=pq.top()+a[i-1];

    pq.pop();

    for(int j=1; j<i && a[i]-a[j-1]>a[i]-a[i-1] ;j++)
      pq.push(a[i]-a[j-1]);

  }
  cout<<a[n]-a[n-1];
}

过去 4 天我一直在尝试解决这个问题，但没有成功。 抱歉英语不好，我只有 14 岁，不是来自说英语的国家。

解决方案(非常感谢 n.m. 和 גלעד ברקן)

V1(n.m.的解决方案)

 using namespace std;

 struct sliding_window{
   int start_pos;
   int end_pos;
   int sum;
   sliding_window(int new_start_pos,int new_end_pos,int new_sum){
     start_pos=new_start_pos;
     end_pos=new_end_pos;
     sum=new_sum;
   }
 };

 class Compare{
 public:
    bool operator() (sliding_window &lhs, sliding_window &rhs){
       return (lhs.sum>rhs.sum);
    }
 };

 int main(){
   int a1, a2, n;
   //input
   cin>>a1>>a2>>n;
   int a[n+1];
   a[0]=a1;
   a[1]=a2;

   queue<sliding_window> leftOut;

   priority_queue< sliding_window, vector<sliding_window>, Compare> pq;
   //add the first two sliding window positions that will expand with time
   pq.push(sliding_window(0,0,a1));
   pq.push(sliding_window(1,1,a2));

   for(int i=2;i<n;i++){
     int target=a[i-1]+1;

     //expand the sliding window with the smalest sum
     while(pq.top().sum<target){
       sliding_window temp = pq.top();
       pq.pop();
       //if the window can't be expanded, it is added to leftOut queue
       if(temp.end_pos+1<i){
         temp.end_pos++;
         temp.sum+=a[temp.end_pos];
         pq.push(temp);
       }else{
         leftOut.push(temp);
       }
     }

     a[i]=pq.top().sum;
     //add the removed sliding windows and new sliding window in to the queue
     pq.push(sliding_window(i,i,a[i]));
     while(leftOut.empty()==false){
       pq.push(leftOut.front());
       leftOut.pop();
     }

   }
   //print out the result
   cout<<a[n-1];
}

V2(文中的解)

int find_index(int target, int ps[], int ptrs[], int n){
  int cur=ps[ptrs[n]]-ps[0];
  while(cur<target){
    ptrs[n]++;
    cur=ps[ptrs[n]]-ps[0];
  }
  return ptrs[n];
}

int find_window(int d, int min, int ps[], int ptrs[]){
  int cur=ps[ptrs[d]+d-1]-ps[ptrs[d]-1];
  while(cur<=min){
    ptrs[d]++;
    cur=ps[ptrs[d]+d-1]-ps[ptrs[d]-1];
  }
  return ptrs[d];
}

int main(void){
  int a1, a2, n, i;
  int args = scanf("%d %d %d",&a1, &a2, &n);
  if (args != 3)
    printf("Failed to read input.\n");

  int a[n];
  a[0]=a1;
  a[1]=a2;

  int ps[n+1];
  ps[0]=0;
  ps[1]=a[0];
  ps[2]=a[0]+a[1];
  for (i=3; i<n+1; i++)
    ps[i] = 1000000;

  int ptrs[n+1];
  for(i=0;i<n+1;i++)
    ptrs[i]=1;

  for(i=2;i<n;i++){
    int target=a[i-1]+1;
    int max_len=find_index(target,ps, ptrs, n);
    int cur=ps[max_len]-ps[0];
    int best=cur;

    for(int d=max_len-1;d>1;d--){
      int l=find_window(d, a[i-1], ps, ptrs);
      int cur=ps[l+d-1]-ps[l-1];

      if(cur==target){
        best=cur;
        break;
      }

      if(cur>a[i-1]&&cur<best)
        best=cur;
    }
    a[i]=best;
    ps[i+1]=a[i]+ps[i];
  }

  printf("%d",a[n-1]);
}

最佳答案

您的优先级队列太大，您可以使用一个小得多的队列。

有一个子数组的优先级队列，例如通过三元组(lowerIndex、upperIndex、sum)，以总和为键。给定大小为 N 的数组 A，对于从 0 到 N-2 的每个索引 i，队列中恰好有一个 lowerIndex==i 的子数组。它的总和是大于最后一个元素的最小可能总和。

在算法的每一步:

1. 将队列第一个元素的和添加为 A 的新元素。
2. 通过扩展其 upperIndex 并更新总和来更新第一个队列元素(以及具有相同总和的所有其他元素)，使其大于新的最后一个元素。
3. 将索引为 (N-2, N-1) 的两个元素的新子数组添加到队列中。

由于上面 p.2 中的重复和，复杂性有点难以分析，但我想应该不会有太多。

关于c++ - 如何在给定前两个数字的级数中找到大于 x 的第 n 个最小子数组和？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55773711/