Rally

Rally

发布于 2023-03-01 | 分类于数学方法、 oi | 3分钟 | 484字数 | 浏览量：

问题描述

有 $n$ 个人居住在数轴的整数位置上，第 $i$ 个人的位置是 $x_i$ 。现需要选定一个整数位置 $p$ ，使所有人移动到 $p$ 并使得所有人的代价之和最小，第 $i$ 个人移动的代价为 $(x_i-p)^2$ ，求最小代价。

输入格式

第一行一个整数 $n$ ，接下来一行有 $n$ 个整数，表示每个人的位置。
$1\le n\le 100,1\le x_i\le 100$

输出格式

输出一个整数，表示最小代价。

样例输入

6
5 2 4 2 8 8

样例输出

解题思路

$\sum_{i=1}^{n}\left(x_i-p\right)^2=\sum_{i=1}^{n}\left(x_i^2-2x_ip+p^2\right)=\sum_{i=1}^{n}x_i^2-2pn\bar{x}+np^2$
因此价值函数是关于p的函数。
$f\left(p\right)=\sum_{i=1}^{n}x_i^2-2pn\bar{x}+np^2$
为了求最小值，对 $f\left(p\right)$ 求一阶导数得到唯一的极值点 $\bar{x}$ 。而由于题目要求的p是整数。所以我们只需要检查极值点 $\bar{x}$ 紧邻的两个整数即可。即 $\left\lfloor\bar{x}\right\rfloor和\left\lceil\bar{x}\right\rceil$ 。
然后分别令 $p=\left\lfloor\bar{x}\right\rfloor$ 和 $p=\left\lceil\bar{x}\right\rceil$ 带入到 $f\left(p\right)$ 中计算即可。最后输出较小的那个结果。

#include<bits/stdc++.h>
using namespace std;
int x[105];

int main(){
    int n,tot=0,t,p;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> t;
        tot+=t;
        x[i]=t;
    }
    p=double(tot)/double(n)+0.5;
    tot=0;
    for(int i = 0; i < n; i++){
        tot+=(x[i]-p)*(x[i]-p);
    }
    cout << tot;
    return 0;
}