思维题+贪心——牛客多校第一场C

时间:2024-12-31 23:03:20
/*
给定一组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 = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + , a + n + , [](int a, int b){return a > b;});
int idx = n;
int las = m;
for(int i = ; i < n; ++i) {
if(i * abs(a[i+] - a[i]) > las) {
idx = i;
break;
} else {
las -= i * abs(a[i+] - a[i]);
}
}
LL num1 = 1LL * (idx * a[idx] - las) * (idx * a[idx] - las);
LL num2 = 1LL * idx * m * m;
for(int i = idx + ; i <= n; ++i) {
num1 += 1LL * a[i] * a[i] * idx;
}
LL tmp = __gcd(num1, num2);
num1 /= tmp, num2 /= tmp;
if(num2 == ) printf("%lld\n", num1);
else printf("%lld/%lld\n", num1, num2);
}