/* 给定一组n维向量 A=(a1/m,a2/m,a3/m ... an/m), 求另一个n维向量 P=(p1,p2,p3...pn),满足sum{pi}=1,使得ans=sum{(ai/m-pi)^2}最大化 并求出这个ans 首先将ai放大m倍 A=(a1,a2,a3...an) 同理 P=(p1,p2,p3...pn),sum{pi}=m 将ai按照降序排序,可以推出大的数减掉x一定比小的数减掉x更优 (ai^2-(ai-x)^2)-(aj^2-(aj-x)^2) =2*x*ai-x^2-(2*x*xj-x^2) =2*x*(ai-aj)>0 可以将原问题转化为从a[]数组里减去总和为m的数,使得最后a[]的平方和最小 那么我们按照贪心策略进行减法,首先将a1减成a1==a2,然后再将a1a2减成a1==a2==a3,依次类推,直到m不够用 最后答案就是减法完成后的a[]的平方和,并在除以m*m即可 */ while(~scanf("%d%d", &n, &m)) { for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1, [](int a, int b){return a > b;}); int idx = n; int las = m; for(int i = 1; i < n; ++i) { if(i * abs(a[i+1] - a[i]) > las) { idx = i; break; } else { las -= i * abs(a[i+1] - a[i]); } } LL num1 = 1LL * (idx * a[idx] - las) * (idx * a[idx] - las); LL num2 = 1LL * idx * m * m; for(int i = idx + 1; i <= n; ++i) { num1 += 1LL * a[i] * a[i] * idx; } LL tmp = __gcd(num1, num2); num1 /= tmp, num2 /= tmp; if(num2 == 1) printf("%lld ", num1); else printf("%lld/%lld ", num1, num2); }