[编程题]堆棋子 中位数

​​https://www.nowcoder.com/questionTerminal/27f3672f17f94a289f3de86b69f8a25b​​

由于x[]和y[]是独立的，所以贡献可以单独考虑

如果选出k个，x[1...k]

那么肯定是去到中位数那个点，所需要的贡献是最小的。

那么就有n^2种不同的目标点，也就是每个x，对应每个y。

然后枚举每一个点到达这个点所需要的最小距离，取个最小的即可。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 50 + 20;
int x[maxn], y[maxn];
int xx[maxn], yy[maxn];
LL sum[52][52][52];
void work() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
        xx[i] = x[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> y[i];
        yy[i] = y[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                sum[i][j][k] = abs(x[k] - x[i]) + abs(y[k] - y[j]);
            }
            sort(sum[i][j] + 1, sum[i][j] + 1 + n);
            for (int k = 2; k <= n; ++k) {
                sum[i][j][k] += sum[i][j][k - 1];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        LL ans = 1e18;
        for (int one = 1; one <= n; ++one) {
            for (int two = 1; two <= n; ++two) {
                ans = min(ans, sum[one][two][i]);
            }
        }
        if (i < n) cout << ans << " ";
        else cout << ans << endl;
    }
}
 
int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code