如何在给出前两个数字的过程中找到大于x的第n个最小子数组和？

Question

我有一个级数“ 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岁，而不是说英语的国家。

解决方案（非常感谢nm和???? ????）

V1（纳米解决方案）

 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]);
}

Answer 1

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

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

在算法的每一步：

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

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