CF1260A Heating

这是一道结论贪心题。结论简单，但是推倒的过程可能不止 入门。（个人感觉，可能有普及）

先说结论，对于每个 都有答案

但是如何得到呢？

这就要有严谨的证明。

首先，看题目，将题面抽象出来，就是这样的：

形象化理解，就是把一个数分成 份，使分出来的数字的平方和最小。

于是，就按生活经验来判断，分成 份且平均的分配会有着更好的 。

首先，对同一个分的份数 ，证明，越平均的分配结果越小。

就等价于证：

证明过程如下：

先左右两边相减。
$$
\frac{a^2}{k}-\sum^{k}{i=1}a_i^2

\frac{(\sum{i=1}^k a_i)^2}{k}- \sum_{i=1}^k a_i^2

\frac{\sum_{i=1}^k a_i^2+\sum_{i=1}^{k-1}\sum^{k}{j=i+1}2a_ia_j}{k}-\sum{i=1}^k a_i^2

\frac{-(k-1)\sum_{i=1}^k a^2_i+\sum_{i=1}^{k-1}\sum^{k}{j=i+1}2a_ia_j}{k}
$$
重点！
$$
\frac{-\sum{i=1}^{k-1}\sum^{k}{j=i+1}(a_i-a_j)^2}{k}

\because -\sum{i=1}^{k-1}\sum^{k}{j=i+1}(a_i-a_j)^2\leq 0,

k>0

\therefore \frac{-\sum{i=1}^{k-1}\sum^{k}{j=i+1}(a_i-a_j)^2}{k}\leq 0

\therefore k(\frac{a}{k})^2\leq \sum{i=1}^k a_i^2
$$

这就证明了在相同 之下，平均分配要比不平均优。

还有， 越大，结果越优。

即证明：

证明是显然的。

所以分配越多越好。

所以， 份全部分配，每一份越平均越好。

可能有读者注意到，前面的命题中，要求 。在本题中，这是不一定的。用鸽巢原理，将剩余的，也平均分到每一份当中。

所以，

的正确性就证明出来了。

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,c,s,mx,lft,ans;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c>>s;
        mx=s/c,lft=s%c;
        ans=(mx+1)*(mx+1)*lft+mx*mx*(c-lft);
        cout<<ans<<endl;
    }
    return 0;
}