求棋盘那题的解题思路

结束2分钟后调好的，也不知道能不能完全通过 #include <iostream> #include<vector> #include <algorithm> using namespace std; int n; long long x[50]; long long y[50]; int test() { long long min_x = 1000000000, min_y = 1000000000, max_x = 0, max_y = 0; for (int i = 0; i < n; i++) { if (x[i] < min_x) min_x = x[i]; if (y[i] < min_y) min_y = y[i]; if (x[i] >max_x) max_x = x[i]; if (y[i] > max_y) max_y = y[i]; } vector<long long> min1(n,1000000000); int num = 0; for (int _x = min_x; _x <=max_x; _x++) { for (int _y = min_y; _y <=max_y; _y++) { vector<long long> dist(n); for (int k = 0; k < n; k++) { dist[k] = abs(_x - x[k]) + abs(_y - y[k]); } std::sort(dist.begin(), dist.end(), less<int>()); for (int k = 1; k < n; k++) { dist[k] = dist[k] + dist[k-1]; } for (int k = 0; k < n; k++) { min1[k] = min(min1[k],dist[k]); } } } for (int i = 0; i < n; i++) cout << min1[i]; return 1; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> x[i]; for (int i = 0; i < n; i++) cin >> y[i]; test(); return 0; }

利用重心 import sys import math n = int(sys.stdin.readline().strip()) x=sys.stdin.readline().split(' ') y=sys.stdin.readline().split(' ') for i in range(0,n):     x[i]=int(x[i])     y[i]=int(y[i]) point=[] nd=dict() for i in range(0,n):     nd[str(x[i])+','+str(y[i])]=nd.get(str(x[i])+','+str(y[i]),0)+1 b=dict(sorted(nd.items(), key=lambda d:d[1], reverse = True)) sum=0 j=0 res=[] tup=[] print (b) for i in range(1,n+1):     while(sum<i):         sum+=list(b.values())[j]         x,y=list(b.keys())[j].split(',')         tup.append([int(x),int(y),list(b.values())[j]])         j+=1     ss1=[0,0]     ss2=0 #    print (tup)     for item in tup:         ss1=[item[0]*item[2]+ss1[0],item[1]*item[2]+ss1[1]]         ss2+=item[2] #     print(ss1,ss2)     xx=round(ss1[0]/ss2)     yy=round(ss1[1]/ss2) #     print(xx,yy)     re=0     sssss=0     for item in tup:         mm=min(item[2],i-sssss)         re+=(abs(xx-item[0])+abs(yy-item[1]))*mm         sssss+=mm     res.append(re) print (res)

对于每位置求每个点到该位置的距离，然后升序排序，然后累加，求最小的向量应该就可以

i个数组合； 对于每种组合找最小值，先找到中点，即sum(x[k])除以i xz， sum(y[k])除以 i yz 然后求每个点到中点的距离，sum(abs(x[k]-xz)+abs(x[k]-xz)) 取每种组合最小值，即为i个数时的最小

我觉得是动态规划 二维数组 

我觉得代码量太大，放弃了或者我思路错了，我以为是求几个点的中心点！

据说是要绕弯2次枚举