小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.
输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数 第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9) 第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)
输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格 如样例所示: 对于1个棋子: 不需要操作 对于2个棋子: 将前两个棋子放在(1, 1)中 对于3个棋子: 将前三个棋子放在(2, 1)中 对于4个棋子: 将所有棋子都放在(3, 1)中
4 1 2 4 9 1 1 1 1
0 1 3 10
def dist_count(ax, by, cx, cy): deta = abs(ax-cx)+abs(by-cy) return deta def main(): n = int(input()) x = list(map(int, input().split(' '))) y = list(map(int, input().split(' '))) dist_sum = [0]*n res = [0]+([int(10e9)]*(n-1)) for i in range(n): for j in range(n): for k in range(n): dist_sum[k] = dist_count(x[i], y[j], x[k], y[k]) dist_sum.sort() for k in range(1, n): dist_sum[k] += dist_sum[k-1] res[k] = min(res[k], dist_sum[k]) print(' '.join([str(i) for i in res])) main()
最终棋子聚点可以等效在点上,
所以只需要枚举所有可能聚点,就能找到最优解
#include <bits/stdc++.h> using namespace std; #define maxn 55 struct node{ int x,y; }a[maxn]; int len(int x,int y,node a){ return abs(x-a.x)+abs(y-a.y); } int b[maxn]; int l[maxn*maxn]; int main(){ int n; scanf("%d", &n); memset(b,0x3f3f3f3f,sizeof b); for(int i=0;i<n;i++) scanf("%d", &a[i].x); for(int i=0;i<n;i++) scanf("%d", &a[i].y); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ l[k]=len(a[i].x,a[j].y,a[k]); } sort(l,l+n); for(int k=1;k<n;k++){ l[k]+=l[k-1]; b[k]=min(b[k],l[k]); } } } cout<<0; for(int i=1;i<n;i++){ cout<<' '<<b[i]; } cout<<endl; return 0; }