Codeforces 问题正确性证明：Boxers（评分 1500）

Question

考虑出现在 Codeforces（评分 1500）中的这个问题：

There are n boxers, the weight of the i-th boxer is ai. Each of them can change the weight by no more than 1 before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.

It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers' weights in the team are different (i.e. unique).

Write a program that for given current values ai will find the maximum possible number of boxers in a team.

It is possible that after some change the weight of some boxer is 150001 (but no more).

Input :The first line contains an integer n (1≤n≤150000) — the number of boxers. The next line contains n integers a1,a2,…,an, where ai (1≤ai≤150000) is the weight of the i-th boxer.

Output :Print a single integer — the maximum possible number of people in a team.

这是我实现的代码，被 Codeforces 接受为正确的提交 (Python 3.7)：

n=int(input())
inputlist=list(map(int, input().split()))
inputlist.sort()
boxerset=set()
for i in inputlist:
    if i-1 not in boxerset and i!=1:
        boxerset.add(i-1)
    elif i not in boxerset:
        boxerset.add(i)
    elif i+1 not in boxerset:
        boxerset.add(i+1)
    else:
        continue
print(len(boxerset))

但是，我无法严格证明这个算法一定会给出正确答案。例如，当输入列表为 [1, 1, 1, 2, 2, 5 , 8] 时，[1, 2, 3, 4, 7, 8]（我的算法）和 [1, 2, 3, 6, 7, 8] 是正确的输出 boxerset，尽管这两种情况的答案都是 6。

我的问题是：

如何证明我的算法是正确的？我的证明将如何证明在所有可能的拳击手合法选择中，我的算法选择的拳击手数量最多（也就是说，我如何证明我不存在其他选择，拳击手的数量可以是大于我的算法所做的选择）?

我试过反证法但无济于事（尽管我认为证明必须具有反证法的自然结构）。

https://codeforces.com/problemset/problem/1203/E

Answer 1

您的代码可以看作是专门的动态程序。

首先，一个结构定理：存在一个最优解，对于每对起始重量为 a_i < a_j 的拳击手组成球队，拳击手的战斗重量 i 小于战斗重量拳击手的体重 j。这是因为如果 a_i + 1 = a_j 和 i 的战斗力是 a_i + 1 并且 j 的战斗力是 a_j - 1，唯一可能发生这种情况。然而，在这种情况下，我们可以让 i 和 j 以他们的起始权重进行战斗，最后的团队将具有相同的权重集。

根据这个结构定理，有一个动态程序按照起始重量从最轻到最重的顺序考虑每个拳击手。最佳子结构是，对于按排序顺序排列的拳击手的前缀，两个相关参数是 1. 从前缀中选择的拳击手的数量 2. 组成球队的拳击手的最重战斗重量（由于结构定理，我们可以假设每个随后的拳击手都必须有更大的战斗重量）。因此，动态程序应该跟踪每个战斗重量限制的最大团队规模。

我们没有写出这个 DP，而是观察到一些解决方案可以被删减。特别是，如果有 k 重量限制 w 拳击手的子解决方案和 k-1 重量限制 w-1 的另一个子解决方案，那么保持第二，因为当我们添加另一个拳击手时，它不会比第一个更好。另一方面，也许我们有一个子解决方案，其中 k 个拳击手的重量限制 w 和 k-1 个拳击手的重量限制 w' < w-1 的子解决方案。如果没有拳击手可以在小于 w 的重量下战斗，那么我们可以再次放弃第二个子解决方案。经过一些案例分析，结果是我们永远不必记住一个以上的子解决方案。

循环的最终版本如下所示。

maxweightonteam = 0
countonteam = 0
for ai in inputlist:
    if ai < maxweightonteam:
        continue
    assert ai + 1 >= maxweightonteam + 1
    maxweightonteam = max(maxweightonteam + 1, ai - 1)
    countonteam += 1
print(countonteam)

就像你的代码一样，这个解决方案反复贪婪地选择下一个最轻的拳击手可以战斗的最小重量。两者都能产生可证明的最佳结果。

Answer 2

David Eisenstat 在他的回答的第二段中的最后一句话“因此动态程序应该跟踪每个战斗重量限制的最大团队规模”启发了我采用替代解决方案。我使用归纳法：

假设在循环迭代时，选择的战斗机的最大战斗重量为k。

The inductive assumption is that this subsequence consists of the maximum team size for weight bound k.

As the inductive step, when the next iterations add the higher fighting weight, this is obviously the maximum team size with weight bound k+1.

要看到这一点，请假设情况并非如此。然后存在一个比我们的算法创建的团队规模更大的子序列。从此列表中删除 k+1 名战士。那么这个列表应该是weight bound k的最大子序列，这导致与归纳假设矛盾。从而证明算法的正确性。

唯一未包括在内的情况是拳击手名单中只有 1 名可能的战士。这个案例很简单，因此证明是完整的。

Codeforces 问题正确性证明：Boxers（评分 1500）

Proof of Correctness of Codeforces Problem: Boxers (rated 1500)

algorithm

proof

proof-of-correctness