题目:

题目

解题思路:

可以先把分母m提到外面去,题目转化为对n个数,你可以改变任意数量的数使他们值变小,但变小的值的总和要等于m,之后再求这n个数的平方和最小值.假设 a<b,则a×a-(a-c)×(a-c)<b×b-(b-c)×(b-c),减去相同的数越大的数他的平方值变化越大,因此贪心选取最大的数改变他的值一定是最优的,由于改变的值不一定为整数,但一定是最大的几个数变成一个相等的值,且这个值一定比其他没改变的数都大,于是我们先把a从大到小排序,然后枚举最大的多少项会变成相等的值,分别求出分子和分母再做约分就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e4+5;
int a[N],sum[N];
ll pw2(int x){return 1ll*x*x;}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1,greater<int>());
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
ll p=0,q=0;
for(int i=1;i<=n+1;i++){
if(sum[i]-i*a[i]>m||i==n+1){
int res=sum[i-1]-(i-1)*a[i-1];
p+=pw2(a[i-1]*(i-1)-(m-res));
q+=1ll*(i-1)*m*m;
for(int j=i;j<=n;j++){
p+=1ll*(i-1)*pw2(a[j]);
}
break;
}
}
ll g=__gcd(p,q);
p/=g;q/=g;
if(q>1)printf("%lld/%lld\n",p,q);
else printf("%lld\n",p);
}
return 0;
}