2019 牛客多校 第一场 C、Euclidean Distance

已知  ，， ，，求 的最小值

------------------------------------------------

1、首先将常数m从式子中提出来

2、 同时乘上一个 m 

，

3、我们知道对于平方和来说，为了使和更小，我们尽量将最大的数字最小化，才能使和最小

比如说 ，我们将3减少一，等到的平方和是 ，将6减少一，得到的平方和是 ，显然将最大数字最小化是最好的选择。

4、但由于 ，所以上一步我们只能优化 为正的项，使他们的最大值尽量小，考虑一种情况，所有大于0的  都已经减少到0了，但此时，就是说还有一部分  没有放入式子中，由于此时所有的  都是非正的了，所以我们可以考虑将括号里面改变一下符号，就变成了  ，为了使这个值尽量小，我们希望尽量少的出现较大的值，所以我们考虑使他的最小值尽量大。也就是让  尽量平均。

5、所以我们发现对于  来说，无论他是正数还是负数，为了使原式尽量小，我们希望让  的最大值尽量小，

6、每次先计算出将目前遍历到的所有元素变为当前元素所花费的代价，如果小于等于m，更新，否则，记一个标记，在这个标记前的都可以更新到同一个值，后面的元素就暴力算。

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[10005];
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int main()
{
	int n, m, t;
	while (scanf("%d%d", &n, &m) > 0)
	{
		int temp = m;
		ll ans = 0;
		for (int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		sort(a + 1, a + 1 + n, greater<int>());
		int index = n;
		for (int i = 1; i <= n; i++)
		{
			int cost = (i - 1) * (a[i - 1] - a[i]);
			if (cost <= m)
				m -= cost;
			else
			{
				index = i - 1;
				break;
			}
		}
		ans = (index * a[index] - m) * (index * a[index] - m);
		for (int i = index + 1; i <= n; i++)
		{
			ans += a[i] * a[i] * index;
		}
		ll ans2 = temp * temp * index;
		int g = gcd(ans, ans2);
		ans /= g, ans2 /= g;
		if (ans2 == 1)
			printf("%lld\n", ans);
		else
		printf("%lld/%lld\n", ans, ans2);
	}
}