题目链接

我的思路：

$X_n = X_1 + \sum\limits_{i = 1}^{n - 1}(ave - A_i)$.

定义$C_j = \sum\limits_{i = 1}^{j - 1}(ave - A_i)$.

于是$X_i = X_1 + C_i$.

原本求$\sum\limits_{i = 1}^{n}|X_i|$.

变成求$min\sum\limits_{i = 1}^{n} |X_1 + C_i|$.

我的代码

scanf("%d", &n);
	for(int i = 1 ; i <= n ; ++ i)
		scanf("%d", &a[i]);
	for(int i = 1 ; i <= n ; ++ i)
	{
		sum += a[i];
	}
	sum /= n;//求平均数ave 
	for(int i = 2 ; i <= n ; ++ i)
	{
		c[i] = c[i - 1] + sum - a[i];//预处理C 
	}
	sort(c + 1 , c + 1 + n);
	int x = c[(n + 1) / 2];
	for(int i = 1 ; i <= n ; ++ i)
	{
		ans += abs(x + c[i]);
	}
	cout<<ans;
	return 0;

---

题解思路：

定义$C_j = \sum\limits_{i = 1}^{j - 1}(A_i - ave)$.

于是$X_i = X_1 - C_i$.

原本求$\sum\limits_{i = 1}^{n}|X_i|$.

变成求$min\sum\limits_{i = 1}^{n} |X_1 - C_i|$.

题解代码：

(两者区别在算答案处的"+"和"-")

scanf("%d", &n);
	for(int i = 1 ; i <= n ; ++ i)
		scanf("%d", &a[i]);
	for(int i = 1 ; i <= n ; ++ i)
	{
		sum += a[i];
	}
	sum /= n;//求平均数ave 
	for(int i = 2 ; i <= n ; ++ i)
	{
		c[i] = c[i - 1] + sum - a[i];//预处理C 
	}
	sort(c + 1 , c + 1 + n);
	int x = c[(n + 1) / 2];
	for(int i = 1 ; i <= n ; ++ i)
	{
		ans += abs(x - c[i]);
	}
	cout<<ans;
	return 0;

---

理论上来说这两个没甚区别 但是为啥我的连样例都过不了