如何在n个整数元素中均匀分配k个点并计算间距d（C#实现）

问题明确 #

已知包含n个元素的列表（索引范围0到n-1），需选出k个起始固定为0的索引，让它们尽可能均匀分布。这里的整数间距d指相邻选中点之间的元素数量（比如0和2之间有1个元素，d=1），且需满足k*d ≤n。

以你给出的例子：n=6（元素0-5）、k=3时，选中索引0、2、4，相邻点间各有1个元素，d=1，此时3*1=3 ≤6，符合要求。

核心计算逻辑 #

要让k个点尽可能均匀分布，d的最大值由两个约束决定：

1. 最后一个选中的索引不能超过n-1：0 + (k-1)*(d+1) ≤n-1，推导得d ≤ (n -k)/(k-1)
2. 满足题目要求的k*d ≤n，推导得d ≤n/k

取这两个值的整数最小值，就是最优的d值。当k=1时，仅需选中索引0，无间距可言，d设为0即可。

C#实现代码 #

public static int CalculateElementSpacing(int n, int k)
{
    if (k <= 0 || k >= n)
        throw new ArgumentOutOfRangeException(nameof(k), "k必须是大于0且小于n的整数");
    
    if (k == 1)
        return 0; // 仅一个起始点，无间距
    
    // 计算两个约束下的最大可能d，取整数最小值
    double constraint1 = (double)(n - k) / (k - 1);
    double constraint2 = (double)n / k;
    int d = (int)Math.Min(constraint1, constraint2);
    
    // 边界情况校验：确保所有约束都被满足
    while (k * d > n || (k-1)*(d+1) > n-1)
    {
        d--;
    }
    
    return d;
}

// 示例调用与索引生成
public static void Main()
{
    int n = 6;
    int k = 3;
    int d = CalculateElementSpacing(n, k);
    Console.WriteLine($"点之间的元素间距d: {d}"); // 输出1
    
    // 生成对应的选中索引列表
    List<int> selectedIndices = new List<int>();
    for (int i = 0; i < k; i++)
    {
        selectedIndices.Add(i * (d + 1));
    }
    Console.WriteLine("分配的索引: " + string.Join(", ", selectedIndices)); // 输出0, 2, 4
}

逻辑验证 #

• 对于n=6，k=3：constraint1=(6-3)/(3-1)=1.5，constraint2=6/3=2，取最小值1.5的整数部分1，符合示例结果。
• 若n=10，k=4：constraint1=(10-4)/(4-1)=2，constraint2=10/4=2.5，取2，选中索引0、3、6、9，相邻点间各有2个元素，d=2，且4*2=8 ≤10，满足要求。

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