algorithm - Codeforces问题: Boxers (rated 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)

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