考虑一下出现在共作用力（1500级）中的这个问题：
有n个拳击手，第i个拳击手的体重是ai。他们每个人在比赛前的体重变化不超过1（体重不能等于零，也就是说，必须保持正）。权重始终是整数。
从人数上选择最大的拳击队是必要的，所有的拳击手在队伍中的权重是不同的（即唯一的）。
编写一个程序，给定给定的当前值，AI将在一个团队中找到最大可能的拳击手数量。
有可能在一些变化后，一些拳击手的体重是150001（但没有更多）。
输入
：第一行包含整数n（1≤n≤150000）-拳击手的数量。下一行包含n个整数a1，a2，…，an，其中ai（1≤ai≤150000）是第i个拳击手的重量。
输出
打印一个整数--一个团队中最大可能的人数。
我实现的代码被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))
但是，我不能严格证明这个算法一定给出了正确的答案。例如，当inputlist为[1，1，1，2，2，5，8]时，[1，2，3，4，7，8]（我的算法）和[1，2，3，6，7，8]都是正确的输出框set，尽管这两种情况的答案都是6。
我的问题是：
如何证明我的算法是正确的？如何证明我的证明，在所有可能的法律选择拳击手，选择我的算法有最大数量的拳击手（这是我如何表明我不存在其他选择，其中拳击手的数量可以大于我的算法所做的选择）？
我试过用矛盾来证明，但没有成功（尽管我认为证明必须具有矛盾证明的自然结构）。
https://codeforces.com/problemset/problem/1203/E
最佳答案
您的代码可以看作是一个专门的动态程序。
首先，一个结构定理：存在一个最优解，对于每一对具有起始重量的拳击运动员来说，使得拳击手的战斗重量小于拳击手a_i < a_j和i的战斗重量是j和a_i + 1 = a_j的战斗重量是i时，才会发生这种情况。然而，在这种情况下，我们可以让a_i + 1和j在他们的起始重量上战斗，最终的队伍将拥有相同的重量。
有了这个结构定理，就有了一个动态程序，它按照从最轻到最重的顺序来考虑每个拳击手。最优子结构是，对于排序后的拳击手前缀，两个相关参数为1。从前缀2中选择的拳击手数一个拳击手组成球队的最重的战斗重量（由于结构定理，我们可以假设每个后来的拳击手必须有一个更大的战斗重量）。因此，动态程序应该跟踪每个战斗重量约束的最大团队大小。
我们没有写出这个dp，而是观察到一些解决方案是可以删减的。特别是，如果有一个子解的重量限制为a_j - 1的拳击手和另一个子解的重量限制为i的拳击手，那么就没有必要保留第二个，因为当我们向它添加另一个拳击手时，它不会比第一个好。另一方面，我们可能有一个子解，其中有一个重量限制j的拳击手，还有一个子解，其中有一个重量限制k的拳击手如果没有一个拳击手可以在体重小于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)
就像你的代码一样，这个解决方案反复贪婪地选择下一个最轻的拳击手可以打的最小重量。两者都产生了可证明的最优结果。