欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]