题解 AT4807 [ABC156C] Rally

RBI_GL · 2021-03-21 10:09:48 · 题解

题意

有 n 个人，第 i 个人处在 x_i 的位置上。现在假设有一个点 P，现已知一个人到 p 点的费用计算公式，确定点 p，使得费用最小，输出最小费用。

思路

由于数据范围很小，可以枚举 p 点的位置，枚举范围是 0 到 102。对于每一个 p，计算出总费用，每次计算最小值即可。

时间复杂度为 O(n^2)。

当然有比这个时间复杂度更优的做法，但对于这道题的数据范围，这个时间复杂度是可以接受的。

Code:

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105];
int cnt = 0;
int ans = 1e9 + 5;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 0; i <= 102; i++) { //点p的位置 
        cnt = 0; 
        for(int j = 1; j <= n; j++) cnt += (a[j] - i) * (a[j] - i); //计算距离和 
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}