SP7015 CFPARTY - Party 题解

前言

这题不难，前提在于你想到了没。

大致题意

有 $n$ 个人，先去掉没有朋友的人，再去掉有 $1$ 个朋友的人，以此类推。求出最后剩下多少人。

抽象题意

构造一张有 $n$ 个结点的图，依次删去度数为 $0$ 到 $n-1$ 的结点，直至无法删除，求出最后最多能剩余几个结点。

思路/解析

若这 $n$ 个点两两相连，则有 $n\times(n-1)\div2$ 条边，这样每个结点的度数都为 $n-1$，都会被删去。

如果删去一条边，就有两个结点的度数变成了 $n-2$，会在别的 $n-2$ 个点之前被删去，删去后剩下的结点的度数变成了 $n-2$，不会被删去。所以最优方案为剩下 $n-2$ 个点。

代码

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