【洛谷题解】攻击火星

经过找规律可以发现答案为 $n-2$ .

以下是证明：

令d[i]为 $i$ 的度数。

考虑一个点 $i$ 不被删去的条件，必然是前面与 $i$ 相邻的点 $j$（可以是多个）被删去，导致 $d[i]$

减小至小于等于 $d[j]$ .

1)易知 $ans!=n$ 。

2)考虑 $ans$ 能否是 $n-1$ ，也就是只删一个点，设这个点为 $i$ 。

因为 $i$ 是唯一被删去的点，所以 $d[i]$ 一定不是最大的，即 $d[i]<n-1$。

其次删去 $i$ 导致其余点的 $d[]$ 均发生改变，从而无法被删去。

即 $i$ 和其余点都相连，$d[i]=n-1$ ，矛盾。

所以 $ans!=n-1$ .

3)我们可以构造出 $ans=n-2$ 的情况：

构造完全图 $G$ ,删去一条边 $( i,j)$ 。这样 $d[i]=d[j]=n-2$ ,其余 $d[]$ 均为 $n-1$ .

首先删去 $VI,Vj$ ，这样其余点各少两条边，$d[]$ 均变成 $n-3$ ,不用被删去。

由此 $n-2$ 是合法的解，也是最大的解，所以答案就是 $n-2$ .