增强算法

Question

我正在寻找一种算法来实现以下行为。如果当前元素和后续元素的总和小于或等于先前元素，则总和被添加到新矢量。下面是例子：

例1：

original vector: 17 | 10 | 6 | 3 | 2 
new vector:  17 | 16 | 5 

出2：

original vector: 41 | 15 | 10 | 5 | 2 
new vector:  41 | 32 

出3：

original vector: 1 | 1 | 1 | 1 | 1 
new vector:  1 | 1 | 1 | 1 | 1 

---

以下作品的代码，但有可能是此代码失败的情况。我很肯定，在一个月内我会忘记我自己的代码的细节。我想使用可靠的代码。有没有一种标准的算法可能在std或boost中做我所提到的？

#include<vector> 
#include<iostream> 

void augmented_sort(const std::vector<double>& invec, std::vector<double>& outvec) 
{ 
    if (invec.empty()) return; 

    outvec.push_back(invec[0]); 

    auto augment = [&invec](double& current, double previous, int& ai) 
    { 
     if (ai >= invec.size()) return false; 
     int start = ai; 
     current = invec[ai]; 
     int ri = 1; 

     while(true) 
     { 
      current += invec[start+ri]; 
      std::cout << "previous = " << previous << std::endl; 
      std::cout << "current = " << current << std::endl; 
      if (current <= previous) 
      { 
       ++ri; 
       ai += 2; 
       std::cout << "ri = " << ri << std::endl; 
       std::cout << "ai = " << ai << std::endl; 
       if (start+ri >= invec.size()) 
        return true; 
      } 
      else if (ai == start) 
       return false; 
      else 
      { 
       current -= invec[start+ri]; 
       return true; 
      } 
     } 
    }; 

    int ai = 1; // absolute index. start from second element. 
    double current; 
    double previous = invec[ai-1]; 

    while (ai < invec.size()) 
    { 
     bool success = augment(current, previous, ai); 
     if (success) 
     { 
      outvec.push_back(current); 
      previous = current; 
     } 
     else 
     { 
      outvec.push_back(invec[ai]); 
      previous = invec[ai]; 
      ai += 1; 
     } 
    } 
} 

int main() 
{ 
    //std::vector<double> invec = {17, 10, 6, 3, 2}; 
    //std::vector<double> invec = {41, 15, 10, 5, 2}; 
    std::vector<double> invec = {1, 1, 1, 1, 1}; 
    std::vector<double> outvec; 
    augmented_sort(invec, outvec); 
    for (double d: outvec) 
     std::cout << "d = " << d << std::endl; 
    return 0; 
} 

Answer 1

我可能是错的，但是你的问题似乎有太小的标准算法。

但是，这里有一些简单的代码，它涉及到在输入向量上循环一次，同时跟踪当前总和，并且只将其添加到输出向量中，如果将当前元素添加到输出向量将导致总和大于最后加入的元素：

void augmented_sort(const std::vector<double>& input, std::vector<double>& output) 
{ 
    if (input.empty()) 
     return; 
    output.push_back(input[0]); 
    int sum = 0; 
    for (int i = 1; i < input.size(); i++) 
    { 
     if (sum + input[i] > output.back()) 
     { 
      output.push_back(sum); 
      sum = 0; 
     } 
     sum += input[i]; 
    } 
    if (input.size() > 1) 
     output.push_back(sum); 
} 

，如果你希望它在任何工作，但按降序排列向量这将需要一些改变（的要求，如前所述，似乎离开那个不清楚预期的行为）。