货仓选址贪心入门
作者:
巷港
,
2022-03-31 12:22:07
,
所有人可见
,
阅读 126
货仓选址
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
cin>>n;
for (int i=0;i<n;i++) cin>>a[i];
sort(a,a+n); //先排序,确保商店坐标有序
int flag; //寻找中位数
if (n%2) flag=a[n/2]; //奇数个数的中位数是排序之后的中间位置
else flag=(a[n/2]+a[n/2-1])/2; //偶数个数的中位数是中间两个数的平均数
int sum=0;
for (int i=0;i<n;i++)
{
sum+=abs(flag-a[i]); //求解中位数和每个商店坐标的绝对值即距离之和
}
cout<<sum<<endl;
return 0;
}
纯暴力TLE过4个样例(4/6)
#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
cin>>n;
for (int i=0;i<n;i++) cin>>a[i];
int ans=0x3f3f3f3f;
for (int i=0;i<n;i++)
{
int sum=0;
for (int j=0;j<n;j++)
{
sum+=abs(a[j]-a[i]);
}
ans=min(ans,sum);
}
cout<<ans<<endl;
return 0;
}