题目概述

CF1428E

解题报告

这就是换了皮的贪心+堆套路题，但是我不会QAQ。

设 $Count(x,k)$ 表示 $x$ 分成 $k$ 堆的最少时间，显然是分成 $k-x\bmod k$ 个 $\lfloor{x\over k}\rfloor$ 和 $x\bmod k$ 个 $\lfloor{x\over k}\rfloor+1$ 最优，而且显然 $Count(x,k+1)$ 比 $Count(x,k)$ 小。

刚开始所有的贡献都是 $Count(a_i,1)$ ，如果把 $1$ 份改成 $2$ 份，就可以减少 $Count(a_i,1)-Count(a_i,2)$ 的时间，然后不难发现这就是个贪心+堆的套路题。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,K,a[maxn+5];LL ans;
int cnt[maxn+5];LL dif[maxn+5];
int si,Heap[maxn+5];

LL Count(int i,int k){
    int x=a[i]/k,B=a[i]%k,A=k-B;
    return (LL)A*x*x+(LL)B*(x+1)*(x+1);
}
inline bool cmp(const int &i,const int &j) {return dif[i]<dif[j];}
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si,cmp))
#define Pop() (pop_heap(Heap+1,Heap+1+si--,cmp))
int main(){
    scanf("%d%d",&n,&K);K-=n;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);ans+=(LL)a[i]*a[i];
        cnt[i]=1;if (cnt[i]<a[i]) dif[i]=Count(i,cnt[i])-Count(i,cnt[i]+1),Push(i);
    }
    for (int i=1;i<=K;i++){
        int x=Heap[1];Pop();ans-=dif[x];
        cnt[x]++;if (cnt[x]<a[x]) dif[x]=Count(x,cnt[x])-Count(x,cnt[x]+1),Push(x);
    }
    printf("%lld\n",ans);return 0;
}