我们对于k取不同特殊值的时候首先分析：

当k=2时，不能有大小为2的完全连通图，那么一条边也不能连，输出0即可。

当k=n时，只需要从原来的完全图中删去1条边即可，故输出n(n-1)/2-1。

当k=n-1时，通过找规律可以发现从原来的完全图中删去2条边即可，故输出n(n-1)/2-2。

下面我们考虑运用一些数学手法解决问题。

想让任意k个点都不是完全连通，我们可以考虑把这n个点分为k-1个部分。

为什么是k-1个？我们考虑此时从这n个点中取k个点时，根据容斥原理，必有两个点在同一个部分里。

把他们放到同一个部分有什么好处？此时我们可以贪心连边，将不同部分的点连边，相同部分的点不连边。这显然是符合要求的，且所有的都连一定是最好的方案。

问题是，我们怎么分才能让能连的边数最多？答案是平均分，我们可以通过数论手段证明或使用调整法证明此结论。

故时间复杂度O(k)。

Tags:greedy,math,constructive algorithms Difficulty:1800