中国建设银行信用卡官网站域名停靠

L1-4 破碎的心，无法挽回的距离

题目描述:

YFffffff 最近在感情上遭受了失败，他的心也破碎成了n块碎片，散落在了数轴上的 n 个位置。

你是一个情感修复师，作为 YFffffff 的好友，你试图将这些破碎的心重新聚集到一个位置，希望能将他们拼凑完整。

然而，移动一颗破碎的心会消耗巨大的情感能量，移动距离的平方就是消耗的能量值（即从位置i移动到位置x，消耗能量为(x−i)2）。

每颗破碎的心代表了 YFffffff 一段零碎的回忆，而将它们聚集到一起的过程，象征着试图修复那些无法挽回的感情。

你的任务是找到一个最佳的目标位置整数 x ，使得将所有破碎的心移动到 x 位置所消耗的总情感能量最少。

然而，即使你完成了任务，这些心是否真的能重新完整，仍然是一个未知数……

输入格式:

一个整数n（1≤n≤100），表示破碎的心的数量。
一个长度为n的数组a，其中a[i]（1≤a[i]≤100）表示第i颗破碎的心的位置。

输出格式:

一个整数，表示将所有破碎的心移动到同一位置所消耗的最小总情感能量。

输入样例1

2
1 4

输出样例1

5

输入样例2

7
14 14 2 13 56 2 37

输出样例2

2354

方法一：因为数据范围不大，故可以遍历每个位置求最小耗能

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{int n,mi=1e9;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);for(int i=a[0];i<=a[n-1];i++){int sum=0;for(int j=0;j<n;j++){sum+=(a[j]-i)*(a[j]-i);}mi=min(sum,mi);}cout<<mi;return 0;}

法二：通过数学方法计算出最优位置是n个位置的平均值，如果求平均值时除不尽，就再算平均值+1的位置的结果，取min。

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{int n,sum=0,res1=0,res2=0,k=1;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}int x,y;x=sum/n;y=sum%n;for(int i=1;i<=n;i++){res1+=(a[i]-x)*(a[i]-x);}if(y!=0){x=x+1;for(int i=1;i<=n;i++){res2+=(a[i]-x)*(a[i]-x);}res1=min(res1,res2);}cout<<res1;return 0;}