如何在C++中实现基于距离准则的高性能分组算法

您好，
我正在寻找一种可实现以下功能的分组算法：
假设我有一个无重复元素的已排序数字数组，例如{0, 2, 5, 6, 7, 10}。
我希望对该数组进行分组，需满足：

• 最小化分组数量；
• 每组内的元素需通过最多n-1个“连接”关联（例如n=3时，0和2是相邻元素，但0和3不是）。

补充说明
换句话说，这里的“相邻”指整数距离。例如，0到2的距离为2（反之亦然），0到3的距离为3。您可以将该问题看作是一组一维点，需要找到最少数量的中心，每个中心覆盖与其距离不超过n/2的点，这样表述应该更清晰。

上述示例有多种分组方式，但符合条件1和2（n=3）的最优分组为{{0,2}, {5,6,7}, {10}}。而{{0}, {2,5}, {6,7}, {10}}的分组数比最优解多一组。若所有排序数字连续，则理想分组数为：

nb_groups* = ceil(v.size() / n);

此外，不同算法可能得到多种解。

目前我的实现步骤如下：

• 计算相邻元素间的距离数组；
• 从向量起始到末尾检查相邻元素的约束条件（见下方代码）。

该实现似乎有效，但我有两个疑问：

• 该实现是否适用于所有场景？（可能未覆盖所有测试用例）
• 若适用，能否对实现进行优化？（比size()-1次迭代更高效，且内存消耗更低）

我设计了一个函数，接收待分组的向量和最大距离参数，返回每组首个元素的索引。

#include <iostream>
#include <vector>

std::vector<int> groupe(const std::vector<int>& at, const int& n);

int main() {
    // Example of input vector
    std::vector<int> in = {0, 2, 5, 6, 7, 10, 11, 22, 30, 50, 51};
    // Try to group with neighbouring distance of 3
    std::vector<int> res = groupe(in, 3);
    

    // Printing the result
    for(const int& a : res) {
        std::cout << a << " ";
    }
    
}

std::vector<int> groupe(const std::vector<int>& at, const int& n) {
    std::vector<int> out;
    
    // Reste keeps tracks of a bigger neighbouring distance (in case we can look for another element to be in the group)
    int reste(0);
    size_t s = at.size() - 1;
    for(int i = 0; i < s; i++) {
        // Computing the distance between element i and i + 1
        int d = at[i + 1] - at[i];
        
        if(d >= n) {
            if(reste == 0) {
                out.push_back(i);
            }
            reste = 0;
        } else {
            if(reste == 0) {
                out.push_back(i);
            }
            reste += d;
            if(reste >= n) {
                reste = 0;
            }
        }
        
    }
    
    if(reste == 0 || reste >= n) {
        out.push_back(s);
    }
    
    return out;
}

输出结果

0 2 5 7 8 9

若原始向量未排序，我认为可先排序再执行上述步骤（或许存在更高效的算法？）。

感谢您抽出时间提供帮助。

内容的提问来源于stack exchange，提问作者Chenoille