算法
贪心+数学常识
思路
众所周知,这是一道初一上学期的零点值问题
1.排序
2.首尾相连,确定范围
3.不知道零点值问题的建议使用百度优先搜索
c++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans;
const ll N=1e5+1e4;
ll a[N];
signed main()
{
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(ll i=1;i<=n/2;i++)ans+=(a[n-i+1]-a[i]);
cout<<ans;
return 0;
}
为什么要排序呢
因为零点值问题就是要求要让最大的与最小的配对,第二大的与第二小的配对…这样才可以使得ans最小
不是这样才使ans最小 是因为由不等式推出的对称关系 然后才证明出来ans最小 建议再去看看零点值问题和不等式推出的区别。
每一个点到中位数的距离,都是满足全局的最有性,而不是局部最优性。 这就是不等式推出的关系,和你的零点值问题没有半毛钱关系。