题解 CF478B 【Random Teams】

本题考数学，难度不高。

首先，如果一个组中有$x$人，那么这个组中朋友的组数就是$\text{C}^2_x=\dfrac{x(x-1)}{2}$。

假设一共分为$k$组，共有$n$人，每一组中的人数分别为$a_1,a_2,a_3,\dots,a_{k-1},a_k$，则朋友的组数为：

$\quad\dfrac{a_1(a_1-1)}{2}+\dfrac{a_2(a_2-1)}{2}+\dfrac{a_3(a_3-1)}{2}+\cdots+\dfrac{a_{k-1}(a_{k-1}-1)}{2}+\dfrac{a_k(a_k-1)}{2}$

$=\dfrac{a_1(a_1-1)+a_2(a_2-1)+a_3(a_3-1)+\cdots+a_{k-1}(a_{k-1}-1)+a_k(a_k-1)}{2}$

$=\dfrac{a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2-a_1-a_2-a_3-\cdots-a_{k-1}-a_k}{2}$

$=\dfrac{a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2-(a_1+a_2+a_3+\cdots+a_{k-1}+a_k)}{2}$

又，由题意知：$a_1+a_2+a_3+\cdots+a_{k-1}+a_k=n$，为定值。

所以问题转化为求$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$的最大值与最小值。

先看最小值。

由柯西不等式得：

$(a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2)(\begin{matrix}\underbrace{1^2+1^2+1^2+\cdots+1^2+1^2}\\\text{k个}1^2\end{matrix})\geqslant(a_1+a_2+a_3+\cdots+a_{k-1}+a_k)^2$

（不明白柯西不等式的同学可以自己百度，这里由于篇幅的原因就不赘述了。）

即

$k(a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2)\geqslant n^2$

移项，得

$(a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2)\geqslant \dfrac{n^2}{k}$

故$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$的最小值为$\dfrac{n^2}{k}$。

此时原式的值为$\dfrac{\frac{n^2}{k}-n}{2}=\dfrac{n^2-kn}{2k}=\dfrac{n(n-k)}{2k}$

故朋友的组数最小为$\left\lceil\dfrac{n(n-k)}{2k}\right\rceil$（向上取整是因为人数必须是正整数）。

再看最大值。

实际上，如果把这个问题当作一个纯粹的数学问题来研究，最大值应该是无穷大。不过在这里，由于人数只能是正整数，所以还是可以有最大值的，只不过比较不好叙述。

现在我们一起来考虑一个事情：函数$f(x)=x^2$的增长速度。

学过导数的同学应该知道，函数$f(x)=x^2$的导数应该是$2x$，也就是说，$x$越大，此函数增长的就越快。

如果没学过导数，没关系，跟我来！

“增长速度”这个名词，现阶段我们可以理解为$f(x+1)-f(x)$的值，也就是$x$每增大$1$，$f(x)$的函数值所增大的值。

照这样理解，函数$f(x)=x^2$的增长速度应该是：

$\quad(x+1)^2-x^2$

$=(x+1-x)(x+1+x)\qquad\qquad$ （平方差公式）

$=2x+1$

因此，如果$x$是一个很大的值，那么$f(x+1)$比$f(x)$多的值也会很大；反之，如果$x$是一个比较小的值，那么$f(x+1)$比$f(x)$多的值也会很小。

所以，$x$越大，此函数增长的就越快。

那这个结论和这道题有什么关系呢？关系大了！

我们现在要求出对于$a_i\in \mathbb{N}^+$，且$a_1+a_2+a_3+\cdots+a_{k-1}+a_k=n$，为定值的时候$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$的最大值。

由之前的结论，我们知道，对于每一个$a_i^2$，都有$a_i$越大，$a_i^2$增长的越快。

那么，我们完全可以使其中的一个数尽可能的大，其余的数尽可能地小啊！（比如其余的数都是$1$）

这样，我们就可以构造出最大值了。

证明如下：

假设此时$a_1=a_2=a_3=\cdots=a_{k-2}=a_{k-1}=$（一个很小的值），$a_k=$（一个很大的值）

如果我们给$a_1,a_2,\dots,a_{k-1}$中的任意一个数加上$x$，则由于$a_1+a_2+a_3+\cdots+a_{k-1}+a_k=n$，为定值，那么$a_k$必须减去$x$。

假设给$a_1,a_2,\dots,a_{k-1}$中的任意一个数加上$x$将会导致$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$增加$p$。

将$a_k$减去$x$导致$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$减少$q$。

那么，由之前的结论，我们知道：$p$一定小于$q$！

这是因为$a_1,a_2,\dots,a_{k-1}$中的任意一个数都远远小于$a_k$，所以加上$x$后增长的值一定小于$a_k$减去$x$之后减少的值。

所以代数式$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$增加了$p$又减少了$q$，减少的比增加的多，显然此时$a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2$变小了。

所以说仅有当$a_1=a_2=a_3=\cdots=a_{k-2}=a_{k-1}=$（一个很小的值），$a_k=$（一个很大的值）的时候，原式有最大值。

在本题中就是$a_1=a_2=a_3=\cdots=a_{k-2}=a_{k-1}=1$，$a_k=n-k+1$的时候，原式有最大值。

此时原式的值为：

$\quad\dfrac{a_1^2+a_2^2+a_3^2+\cdots+a_{k-1}^2+a_k^2-(a_1+a_2+a_3+\cdots+a_{k-1}+a_k)}{2}$

$=\dfrac{\begin{matrix}\underbrace{1^2+1^2+1^2+\cdots+1^2+1^2}\\\text{k-1个}1^2\end{matrix}+(n-k+1)^2-n}{2}$

$=\dfrac{k-1-n+(n-k+1)^2}{2}$

$=\dfrac{(n-k+1)^2-(n-k+1)}{2}$

$=\dfrac{(n-k+1)(n-k)}{2}$

（特别地，这里不需要取整，原因是$n-k+1$和$n-k$中必定有一个偶数。）

需要注意的是，我们需要特判$n<k$的情况。

至于代码，就不贴了，在明白了以上知识以后，写出一篇AC代码是很容易的啦～～

纯数学题贴什么代码啊（

$\text{The end}$