题解 P1416 【攻击火星】

这题考构造，难度适中。

题目链接

首先来说说什么是“度”。

在这里，一个点的“度”指的就是与这个点连接的边的数量。

比如下图中，点$A$的度是$3$，点$B$、点$C$的度是$2$，点$D$的度是$1$。

接下来，开始讲题。

本蒟蒻看到题后，第一反应是不会做，第二反应就是拿几组数据试一下，找找规律。

当$n=1$时，唯一的一个点一定会被删掉，故答案为$0$。

当$n=2$时，这两个点要么连着，要么分开。连着的时候两个点的度都是$1$，分开的时候两个点的度都是$0$。所以，不管怎样，答案都是$0$。

当$n=3$时，样例已经解释清楚了，用队列法，答案是$1$。

当$n=4$时，我们可以试着学学样例，用队列法构造这样的图：

此时，由于没有度为$0$的点，所以外星人会直接删除度为$1$的点，即$A,D$。

然后图就变成了这样：

此时，外星人应该删除度为$2$的点，但上一步操作使得$B,C$的度都变成了$1$，外星人无法删除$B,C$，故$B,C$幸存了下来。

故答案为二。

难道题目就是想让我们用队列法？当然不是！

当$n=5$时，如果我们继续用队列法，那么会变成这样：

我们惊讶地发现：点$C$居然也被删除了！！！

于是，队列法宣告失败。

不过，在我们前面的枚举中，我们似乎看出了什么端倪：

（下面的表格在题解区有可能会爆，建议去博客区观看。如果表格没爆，请忽略这句话。）

$\begin{matrix}n=2&ans=0&ans=n-2\\n=3&ans=1&ans=n-2\\n=4&ans=2&ans=n-2\end{matrix}$

莫非......答案真的是$n-2$ ？

下面就让我们一起来看一看吧。

以$7$个点为例：

我们先选取两个点$A,B$，再把$A,B$与除了彼此之外的所有点相连。

对于剩下的五个点，把每个点与其余的点相连。

（已经帮各位标过每个点的度了～）

然后，邪恶的外星人删除了度最小的点，即$A,B$。

此时，外星人刚刚删除了两个度为$5$的点，应该删除度为$6$的点。

但是删除$A,B$后，剩下的五个点的度都变成了$4$，外星人无法删除它们，所以这五个点留了下来。

下面证明对于所有情况，都有$ans=n-2$。

$1.$ 显然，$ans\neq n$。

$2.$ 假设 $ans=n-1$，那么只删除了$1$个点，设为$A$。

由于在$n$个点中，每个点最多只能与除了自身之外所有的点相连，所以每个点的度都不超过$n-1$。

又，点$A$被删去了，所以点$A$的度小于$n-1$。

如果删去点$A$影响不到其他点的度，那么必有点$A$的度为$0$。

于是，删去点$A$后，外星人完全可以删去其他的点，这是因为其他点的度一定大于等于$0$，矛盾。

所以删去点$A$必然影响其他点。

又因为外星人只删除了一个点，至多使其他点的度减$1$。

而之前已经说过点$A$的度小于 $n-1$，一定存在至少$1$个点与点$A$不相连。（如果与其余点都相连那么点$A$的度就是 $n-1$ 了）

又因为点$A$被删去了，所以点$A$的度一定小于其余的点。

所以外星人删去点$A$后，与点$A$不相连的点不受影响，它们的度仍然大于点$A$的度，所以外星人仍然能够继续删除那些与点$A$不相连的点。

所以$ans\neq n-1$。

$3.ans=n-2$

这个之前已经说过构造方法了，是成立的。

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

不过，有一个地方需要注意：当$n<2$，即$n-2<0$时，答案仍然是$0$。

最后，上代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<2){
        cout<<0;
    }
    else{
        cout<<n-2;
    }
    /*
    当然也可以这么写：
    cout<<max(0,n-2);
    这个语句在n-2<0时自动输出0与n-2中小的那个，而n-2<0，所以会输出0。
    */
    return 0;
}

$\text{The\ end.}$