AcWing 104. 货仓选址
原题链接
简单
作者:
Nazarena
,
2021-02-04 16:35:43
,
所有人可见
,
阅读 433
算法1
(暴力枚举) $O(n^2)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[100000],n,num;
long long sum,min;
cin >> n;
for(int i=0;i<n;i++)
cin >> a[i];
sort(a, a+n);
for(int i=1;i<=a[n-1];i++)
{
sum = 0;
for(int j=0;j<n;j++)
sum += abs(a[j]-i);
if(i == 1)
min = sum;
else
{
min = min < sum ? min : sum;
}
}
cout << min;
return 0;
}
算法2
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[100000],n;
long long sum = 0;
cin >> n;
for(int i=0;i<n;i++)
cin >> a[i];
sort(a, a+n);
for(int i=0;i<n;i++)
sum += abs(a[(n-1)/2]-a[i]);
cout << sum;
return 0;
}