SP7015 题解

· · 题解

这题就一个个算过去就行了。
若 n=1，那么这个人肯定没朋友，人就走了，剩下 0 人。
若 n=2，无论他们两人是不是朋友，两人都会走，剩下 0 人。
若 n=3，（由样例可知，剩下 1 人）人还没走的时候，无法确定他们是否为朋友，所以此时所有人都有朋友，没人离开。然后是有 1 个朋友的人离开，此时只能是有两个人互为朋友，所以离开 2 人，剩下 1 人。 若 n=4，和 n=3 的情况类似，在朋友数为 0 和 1 的时候无法确定他们是否为朋友，无人离开。有 2 个朋友的人离开时，有 2 个人会离开，剩下 2 人，这下他们俩要嘛不是朋友，要嘛是朋友，此时只有 0 或 1 个朋友的人离开的时候已经过去了，他们也没法离开了。
若 n=5，依照上面的情况可推出最后剩下了 3 人。

观察上述例子，可以猜测：n\le2 时，剩下 0 人；n\ge2 时，剩下 n-2 人。

或者从图论的角度思考，将这 n 个人变为一张有 n 个结点的无向图，那么题意就变成了：依次删除度数从 0 到 n-1 的结点，求最后剩下几个节点。

假设每个点都两两相连，此时每个点的度数为 n - 1，删去一条边，那么就有两个点的度数会变为 n - 2，这两个点会被先删去，接着每个点的度数会变为 n - 3。接下来应删除度数为 n - 1 的结点，但此时每个点的度数都为 n - 3，无法删除，那么可以得出：剩余 n - 2 个结点。

但要特判，从上面一个个推的结果来看，答案为 \max(n - 2, 0)。

#include <bits/stdc++.h>
using namespace std;
int n, t;
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        cout << max(n - 2, 0) << '\n';
    }
    return 0;
}