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

问题描述 投票：6回答：3

我有一个进展“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和Gilad Barkan）

B1（上午解决）

 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（Gilad Barkan的解决方案）

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]);
}
c++ algorithm data-structures
3个回答
1
投票

您的优先级队列太大，您可以使用更小的队列。

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

在算法的每一步：

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

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

2
投票

尝试每个相关的子阵列长度来查找下一个元素可能就足够了。如果我们在每个长度上搜索最佳窗口，我们可以使用O(n * log(n) * sqrt(n))解决方案。

但是我们可以通过观察每个子阵列长度具有低的界限指数来做得更好，该指数随着n的增加而不断增加。如果我们保持指向每个子数组长度的最低索引的指针，并且每次只是向上迭代，我们保证每个指针最多会增加n次。由于有O(sqrt n)指针，我们有O(n * sqrt n)总迭代次数。

随后是指针概念的草稿。

UPDATE

对于实际提交，find_index函数被转换为另一个增加速度的指针。 （提交here，用户名“turnerware”; C代码here。）

let n = 100000

let A = new Array(n)

A[0] = 2
A[1] = 3

let ps = new Array(n + 1)

ps[0] = 0
ps[1] = A[0]
ps[2] = A[0] + A[1]

let ptrs = new Array(n + 1).fill(1)

function find_index(target, ps){
  let low = 0
  let high = ps.length
  while (low != high){
    let mid = (high + low) >> 1
    let cur = ps[mid] - ps[0]
    if (cur <= target)
      low = mid + 1
    else
      high = mid
  }
  return low
}

function find_window(d, min, ps){
  let 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]
}

let start = +new Date()

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

  for (let d=max_len - 1; d>1; d--){
    let l = find_window(d, A[i-1], ps)
    let 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]
}

console.log(A[n - 1])
console.log(`${ (new Date - start) / 1000 } seconds`)

只是为了好玩和参考，这打印了与元素对应的序列和可能的索引间隔：

let A = [2, 3]
let n = 200
let is = [[-1], [-1]]
let ps = [A[0], A[0] + A[1]]
ps[-1] = 0

for (let i=2; i<n + 1; i++){
  let prev = A[i-1]
  let best = Infinity
  let idxs
  
  for (let j=0; j<i; j++){
    for (let k=-1; k<j; k++){
      let c = ps[j] - ps[k]
      if (c > prev && c < best){
        best = c
        idxs = [[k+1,j]]
      } else if (c == best)
        idxs.push([k+1,j])
    }
  }
  
  A[i] = best
  is.push(idxs)
  ps[i] = A[i] + ps[i-1]
}

let str = ''

A.map((x, i) => {
  str += `${i}, ${x}, ${JSON.stringify(is[i])}\n`
})

console.log(str)
0
投票

对我来说看起来像一个滑动窗口问题。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    if(argc != 4) { 
        cout<<"Usage: "<<argv[0]<<" a0 a1 n"<<endl;
        exit(-1);
    }
    int a0 = stoi(argv[1]);
    int a1 = stoi(argv[2]);
    int n  = stoi(argv[3]);
    int a[n];                           // Create an array of length n
    a[0] = a0;                          // Initialize first element
    a[1] = a1;                          // Initialize second element
    for(int i=2; i<n; i++) {            // Build array up to nth element
        int start  = i-2;               // Pointer to left edge of "window"
        int end    = i-1;               // Pointer to right edge of "window"
        int last   = a[i-1];            // Last num calculated
        int minSum = INT_MAX;           // Var to hold min of sum found
        int curSum = a[start] + a[end]; // Sum of all numbers in the window
        while(start >= 0) {             // Left edge is still inside array
            // If current sum is greater than the last number calculated
            // than it is a possible candidate for being next in sequence
            if(curSum > last) {         
                if(curSum < minSum) {   
                    // Found a smaller valid sum 
                    minSum = curSum;
                }   
                // Slide right edge of the window to the left
                // from window to try to get a smaller sum. 
                // Decrement curSum by the value of removed element
                curSum -= a[end];
                end--; 
            }   
            else {
                // Slide left edge of window to the left
                start--;
                if(!(start < 0)) {
                    // Increment curSum by the newly enclosed number
                    curSum += a[start];
                }   
            }   
        }   
        // Add the min sum found to the end of the array.
        a[i] = minSum;   
    }   
    // Print out the nth element of the array
    cout<<a[n-1]<<endl;
    return 0;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.