AcWing 3580. 整数配对
原题链接
中等
作者:
猪啊猪
,
2021-05-27 19:16:42
,
所有人可见
,
阅读 499
//斗胆小小证明一下:
//先排序
//如排序后为: a,b,c,d
//当a,b为一组;c,d为一组时
//res1 = (b-a)+(d-c) = b+d-(a+c)
//当a,c为一组;b,d为一组时
//res2 = (c-a)+(d-b) = (c+d)-(a+b)
//(当a,d一组;b,c一组时 res3 = res2 = (c+d)-(a+b))
//易知b+d<c+d,a+b<a+c 所以res1<res2
//同理 当以其他组合时,依然res1最小
//所以当n为偶数时,排序后相邻对作为一组答案最小
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> q;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
q.push_back(x);
}
sort(q.begin(),q.end());
int res = 0;
for(int i=0;i<n-1;i+=2)
{
int x = q[i];
int y = q[i+1];
res+=(y-x);
}
cout<<res<<endl;
}