104. 货仓选址——绝对值不等式的运用,中位数巧用
程序员文章站
2022-07-12 21:35:14
...
题解
|a-x|+|b-x|>=|a-b|
当只有a,b两个商店时,仓库建在a,b之间可以取得最小值
扩展到n个物品的时候
- 当n为偶数时,ans=|x-a1|+|x-an|+|x-a2|+|x-an-1|…,>=|a1-an|+|a2-an-1|
两两配对,x必须在a1,an中间,a2,an-1中间…,x可以取an/2或者an/2+1 - 当n为奇数的时候,同理除了中位数那个其他两两配对,当x位于中位数时取得最小值
AC代码
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define gcd(a,b) __gcd(a,b)
#define ft first
#define sd second
#define endl '\n'
#define PI acos(-1.0)
#define lcm(a,b) a/gcd(a,b)*b
#define INF_INT 0x3f3f3f3f
#define INF_LONG 4557430888798830399
//inline void print(__int128 x)
//{
// if(x<0) {putchar('-'); x=-x;}
// if(x>9) print(x/10);
// putchar(x%10+'0');
//}
//inline int read()
//{
// int s=0,x=1;
// char ch=getchar();
// while(ch<'0'||ch>'9') {if(ch=='-') x=-1; ch=getchar();}
// while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar(); }
// return s*x;
//}
const int N = 1e5+9;
int a[N];
int v[N];
int main()
{
int n;
cin>>n;
ll ans=0,maxi=-1,maxcnt=-1;
for(int i=0; i<n; i++)
{
cin>>a[i];
v[a[i]]++;
}
sort(a,a+n);
int x=a[n/2];
for(int i=0; i<n; i++)
{
ans+=abs(a[i]-x);
}
cout<<ans<<endl;
return 0;
}
注意
我这里数组是从0开始存储,如果从1开始x=a[n/2+1]
上一篇: python多进程与多线程
下一篇: 入门并行编程MPI(二)