堆棋子题解

可以明确的是，所有备选格子的坐标必然在 x[]和y[]选取，优先可以计算出所有点到所有备选格子的距离，然后进行排序，使用前缀和可以快速取出每个备选格子包含不同棋子数的距离之和。最后取最小值即可。
时间复杂度 O(n^3logn)
空间复杂度 O(n)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 55;
int x[maxn], y[maxn], n;
long dist[maxn], ans[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &y[i]);
    memset(ans, 0x3f, sizeof(ans));

    // 目标点的坐标必然在x[], y[]中选取，所以最多有n*n个备选点
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) { 
            for (int k = 1; k <= n; k++) {
                dist[k] = abs(x[i]-x[k]) + abs(y[j]-y[k]);
            }
            sort(dist+1, dist+n+1);

            for (int i = 1; i <= n; i++) { 
                dist[i] += dist[i-1]; // default: dist[0] = 0;
                ans[i] = min(ans[i], dist[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%ld ", ans[i]);
    printf("\n");
    return 0;
}