CF(Div. 1 + Div. 2) E. Carrots for Rabbits（优先队列+贪心）

原题链接

题意：

给你n个数，要你把n个数切成k个。求切后最小平方和。

题解

一开始就想着把每个数放进优先队列里，然后把最大的平分，再放回去。但这样是错的。如1 3 100 ：33 33 34会更好。

---

用优先队列维护结构体{a,b,c}。b存的是读入的数。a表示给这个数切（c刀-c+1刀）这个数的平方差值，c代表现在切的刀数。并对a进行大到小排序。

反正就是一刀一刀的切，取差值最大的那个。

#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node { ll a,b,c; friend bool operator<(node x,node y) { return x.a<y.a; } }; priority_queue<node>q; ll cut(int a,int x)//把a切成x刀，返回平方差值 { ll m=a/x,t=a%x;//t代表有t个数是m+1。。。。（x-t）个数是m return t*(m+1)*(m+1)+(x-t)*m*m; } int main() { int n,k; cin>>n>>k; ll ans=0; for(int i=1;i<=n;i++) { ll x; cin>>x; ans+=x*x; q.push({cut(x,1)-cut(x,2),x,2}); } for(int i=n;i<k;i++) { auto x=q.top(); q.pop(); ll a=x.a,b=x.b,c=x.c; ans-=a; q.push({cut(b,c)-cut(b,c+1),b,c+1}); } cout<<ans; return 0; }