algorithm - 如何证明这个贪心算法的最优性？

Question

给定 N 个整数。这些数字中的每一个都可以增加或减少一次不超过给定的正整数 L。在每次操作之后，如果任何数字变得相等，我们将它们视为一个数字。问题是计算最小的不同整数集的基数。

约束:N <= 100，L <= 3200，整数在 [-32000, 32000] 范围内

示例:N = 3，L = 10 11 21 27

1) 11 增加 10 => 21 21 27
2) 将 27 减 6 => 21 21 21

答案是 1。

C++ 语言算法:

sort(v.begin(), v.end());
// the algo tries to include elements in interval of length 2 * L
int ans = 0;
int first = 0; 
for(int i = 1; i < N; ++i) {
    if(v[i] - v[first] > 2 * L) { // if we can't include i-th element 
        ans++;                    // into the current interval   
        first = i;                // the algo construct new 
    }
}
ans++;
printf("%d", ans);

我试图理解为什么这种贪心算法是最优的。感谢您的帮助。

Answer 1

重构后，我们尝试用尽可能少的基数 2*L + 1 间隔覆盖输入中出现的数字集。你可以想象，对于一个区间[C - L, C + L]，其中的所有数字都调整为C。

给定任何按排序顺序排列的区间列表，我们可以在 k 中归纳地证明，仅考虑前 k 区间，前 k > of greedy 至少涵盖了尽可能多的输入。基本情况 k = 0 很简单。归纳地，贪婪覆盖下一个未覆盖的输入元素，并尽可能多地覆盖；任意解决方案中覆盖其下一个未覆盖输入元素的区间必须不在贪婪之后，因此任意解决方案不再有覆盖。