CodeForces 710B Optimal Point on a Line

递推。

先对$a[i]$进行从小到大排序。

然后计算出每个点左边所有点到这个点的距离之和$L[i]$，以及右边每个点到这个点的距离之和$R[i]$。

这两个都可以递推得到。

$L\left[ i \right] = L\left[ {i - 1} \right] + \left( {i - 1} \right)×(a\left[ i \right] - a[i - 1])$，

$R\left[ i \right] = R\left[ {i + 1} \right] + \left( {n-i} \right)×(a\left[ i+1 \right] - a[i])$。

然后寻找到$L[i]+R[i]$最小的位置，最后输出那个位置即可。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

const int maxn=3e5+;

LL a[maxn],L[maxn],R[maxn],Min;

int n;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lld",&a[i]);

    sort(a+,a++n);

    for(int i=;i<=n;i++) L[i]=L[i-]+(i-)*(a[i]-a[i-]);

    for(int i=n;i>=;i--) R[i]=R[i+]+(n-i)*(a[i+]-a[i]);

    Min=; for(int i=;i<=n;i++) if(L[i]+R[i]<L[Min]+R[Min]) Min=i;

    printf("%lld\n",a[Min]);

    return ;

}

巴特西

CodeForces 710B Optimal Point on a Line

最新文章

热门文章