自动搬运

查看原文

来自洛谷，原作者为

	chu_K 单调

搬运于2025-08-24 22:20:37，当前版本为作者最后更新于2021-03-12 18:54:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Sol

看到题目，我们首先想到dp，其中 $f[i][j]$ 表示将前 $i$ 栋楼中的学生进行 $j$ 次操作所得到的最小吵闹值。那么最终的答案就是 $f[m][k]$ 。

dp方程也很好推： $f[i][j]=min(f[i][j],f[i-1][k]+sol(i,j,kk))$

dp部分代码：

    for (i=1; i<=m; i++)
      for (j=0; j<=k; j++)
         for (kk=0; kk<=j; kk++)
            f[i][j]=min(f[i][j],f[i-1][kk]+cmf(i,j,k));

那么本题的一个难点就是怎样进行操作是最优的，观察样例我们不难发现，将学生尽量均分是最优的。简化一下题目，进行 $k$ 次操作，其实就是将学生分为 $k+1$ 分。不难发现均分后的最小值肯定是 $\frac{n}{k+1}$ ， 那么最大值也就是 $1+\frac{n}{k+1}$ 这样计算起来就很简单了。

Tips: 若使用子程序进行计算千万别忘了开 long long 否则会WA两个点。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long//别忘了
using namespace std;
int n,m,k,i,j,x,kk,kkk,num,sum,mon,a[555],f[555][555];

int cmf(int i, int j, int kk)
{
        kkk=j-kk;
        mon=a[i] / (kkk+1);//最小值
        sum=(mon+1) * (kkk+1) - a[i];
        num=(kkk+1) - sum;
        sum=sum * mon * (mon+1) / 2 + num * (mon+1) * (mon+2) / 2;
        return sum;
}//计算sol

signed main()
{
        cin >> n >> m >> k;
        for (i=1; i<=n; i++)
        {
                cin >> x;
                a[x]++;
        }

        for (i=1; i<=m; i++)
                for (j=0; j<=k; j++)
                        f[i][j]=0x3f3f3f3f;//预处理

        for (i=1; i<=m; i++)
                for (j=0; j<=k; j++)
                        for (kk=0; kk<=j; kk++)
                                f[i][j]=min(f[i][j],f[i-1][kk]+cmf(i,j,kk));//dp
        cout << f[m][k];
}