货仓选址贪心入门
作者:
巷港
,
2022-03-31 12:22:07
,
所有人可见
,
阅读 127
货仓选址
#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;
}