https://codeforces.com/problemset/problem/1428/E
是个贪心,真的玄学阿。不太明白是怎么回事。
样例能看出来,肯定不是只把一个分成两份,那就枚举。分成两份的也有机会分成三份,这样就公平了,谁贡献大就分谁
#include<iostream> #include<queue> #include<set> #include<vector> using namespace std; const int maxn = 2e5+1; typedef long long ll; ll list[maxn]; struct Node{ ll x,len; ll tim; Node(ll a,ll b,ll c):x(a),tim(b),len(c){} }; bool operator < (Node a,Node b){ return a.len < b.len; } priority_queue<Node>que; ll cal(ll a,ll b){//a分成b个 ll cnt = a % b; ll x = a/b; ll ans = (x*x)*(b - cnt) + ((x+1)*(x+1))*cnt; return ans; } int main(){ int n,k; cin>>n>>k; ll x; ll ans = 0; for(int i=1;i<=n;i++){ cin>>x; ans += x*x; ll c = cal(x,1) - cal(x,2); que.push(Node(x,2,c)); } for(int i = 0;i<k - n;i++){ Node a = que.top(); que.pop(); ans -= a.len; ll c = cal(a.x,a.tim) - cal(a.x,a.tim + 1); que.push(Node(a.x,a.tim+1,c)); } cout<<ans<<endl; return 0; }