题意： 有n个萝卜 ，每根萝卜长度不一样，现在将这些萝卜分为k段 这k根萝卜每根萝卜的花费是长度的平方，求最小的花费。 思路： 原本想的是放进将萝卜放进大根堆，然后取最大的对半分，其实这样是不正确的，hack数据：3 5 10 3 1 如果按照对半分的思路来 就是分为 2 3 5 3 1 ，然而最优解是 3 3 4 3 1，那就是不正确的，那么我们换一种思路，如果知道每一根萝卜分为z段 ，那么每根萝卜的最优解就是均分，那么有个大胆的想法就是将每个萝卜的当前最小花费和多分一段的最小花费的差值放进大根堆里面，然后执行k-n次，每次就减去最大值，不得不说太优秀了这个想法。 ac代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node{ ll a; ll b; ll c; bool operator <(const node&W)const { return a<W.a; } }; priority_queue<node>q; ll get(ll x,int k) { ll aver=x/k; ll time=x%k; return time*(aver+1)*(aver+1) + aver*aver*(k-time); } int main() { ll n,k; cin>>n>>k; ll res=0; for(int i=0;i<n;i++) { ll x; cin>>x; res+=1ll*x*x; q.push({get(x,1)-get(x,2),x,2}); //cout<<get(x,1)-get(x,2)<<endl; } int ct=k-n; // cout<<ct<<endl; for(int i=0;i<ct;i++) { auto t=q.top(); q.pop(); ll a=t.a; ll b=t.b; ll c=t.c; //cout<<a<<' '<<b<<' '<<c<<endl; res-=a; q.push({-get(b,c+1)+get(b,c),b,c+1}); } cout<<res<<endl; return 0; }