我是文章标题

· · 题解

题解区目前似乎都是背包dp，但是题目只需要最终状态，所以我们同样可以推式子贪心求解。本质思想都是一样的。

题面

题面

思路

由于不知道之后这栋楼还会入住几次，我们较难通过一边加入人一边计算答案，所以我们将答案放在所有人都入住后再处理。

我们设一段长度为 x 的入住所产生的吵闹指数之和为 S(x)=1+2+3+\cdots+x=\frac{x(x+1)}{2}。若将一栋楼的 m 次入住按每次清空操作作为分界线分成 f 段，各段长度为 x_1, x_2, \cdots, x_f（满足 x_1 + x_2 + \cdots + x_f = m 且 x_i ≥ 1），则总噪音和为：

total=\sum_{i = 1}^{f}S(x_i)

容易证明的是，尽量让操作均摊使每次清空一栋楼之前和最后一次入住的吵闹指数尽量相同是最优的。

更形式化的讲：当 x_1, x_2, \cdots, x_f 中任意两个数的差不超过 1（即尽可能平均）时，total 最小。 ::::info[证明] 假设存在某分段方式，其中两段长度为 a 和 b（a ≥ b + 2），此时这两段的吵闹指数和为 S(a)+S(b)。若调整这两段为 a' = a - 1 和 b' = b + 1（总和仍为 a + b），新的吵闹指数和为 S(a')+S(b')，那么设两者的差为 c，则：

c = S(a')+S(b')-S(a)-S(b) = \frac{(a-1)a}{2}+\frac{(b+1)(b+2)}{2}-\frac{a(a+1)}{2}-\frac{b(b+1)}{2} = \frac{(a^2-a)+(b^2+3b+2)}{2}-\frac{(a^2+a)+(b^2+b)}{2} = \frac{-2a+2b+2}{2} =-a+b+1

由于 a ≥ b + 2，所以 -a+b+1≤-1。由此可得即尽可能平均分段时总吵闹指数和最小。
:::: 同理，这个结论可以作用到全局所有楼，且清空更多次一定是不劣的。

我们可以根据这个结论计算出每栋楼的入住分为多少块时的吵闹指数最小总和。我们要尽量使每栋楼总和最小，就要使每次清空能减少的尽可能的多。计算能减少的吵闹指数后使用优先队列优先取最大的减少值增加所对应的楼的清空次数，时间复杂度 O(n+(k+m)\log m)。

代码

#include <bits/stdc++.h>
using namespace std;
#define QwQ return
#define egg 0;
#define retrun return
#define int long long
#define F(a,b,c) for(int a=b;a<=c;++a)
#define awa signed main(){mian();}
//  ? ? ?
// ?     ?
//?       ?
//?       ?
//       ?
//     ?
//    ?
//    ?
//
//    ?
constexpr int maxn=1e2+14;
namespace IO
{
    inline int read(){
        int x=0,f=1;
        char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;ch=getchar();
    }while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';ch=getchar();}
    return x*f;}
    inline void print(int x){
        if(x<0){putchar('-');x=-x;}
        if(x>9){print(x/10);}
        putchar(x%10+'0');}
}using namespace IO;
int n,m,k;
int b[maxn];
typedef struct ppp
{
    int c,f,idx;
    bool operator<(const ppp& d) const
    {
        return c<d.c;
    }
} ppp;
priority_queue<ppp> q;
inline int calc_sum(int n,int f)
{
    if(f==0) return 0LL;
    int q=n/f;
    int r=n%f;
    return r*((q+1)*(q+2)/2)+(f-r)*(q*(q+1)/2);
}
int a;
signed mian()
{
    n=read(),m=read(),k=read();
    F(i,1,n)
    {
        a=read();
        ++b[a];
    }
    F(i,1,m)
    {
        if(b[i]==0)continue;
        int f=1;
        int sum1;
        int sum2;
        if(f!=1);
        {
            sum1=calc_sum(b[i],f);
            sum2=calc_sum(b[i],f+1);
        }
        int c=sum1-sum2;
        q.push({c,f,i});
    }
    while(k>0&&!q.empty())
    {
        ppp curr=q.top();
        q.pop();
        int idx=curr.idx;
        int f=curr.f;
        int new_f=f+1;
        int sum_f=calc_sum(b[idx],f);
        int sum_new=calc_sum(b[idx],new_f);
        int next_c=sum_new-calc_sum(b[idx],new_f+1);
        q.push({next_c,new_f,idx});
        --k;
    }
    int ans=0;
    while(!q.empty())
    {
        ppp curr=q.top();
        q.pop();
        ans+=calc_sum(b[curr.idx],curr.f);
    }
    print(ans);
    QwQ egg
}
awa