题解

难度：中等

知识点：暴力求解

棋子只能上下左右移动，所以移动的步数即操作次数为两个位置的曼哈顿距离
坐标(x1,y1)的i点与坐标(x2,y2)的j点的曼哈顿距离为d(i,j)=|x1-x2|+|y1-y2|

本题是要求解棋盘上出现一个格子中至少k个棋子的最少操作。那这k个棋子出现在那个格子呢，最少的操作数可能出现在棋盘上的任何一个格子么？
先来看个例子：
先来看看一维的情况，如有四颗棋子x=[1,2,4,9]，要将这4颗棋子移到一个格子上，格子坐标范围为[1:10]，结果如下

可以发现规律：
1）当四颗棋子都要移到格子x=i时，相对于四颗棋子都要移到格子x=i-1的基础上，在格子x=i左边的棋子的步数都+1，在格子x=i上及右边的棋子步数都-1
2）由规律1）可以总结到对于四颗棋子都移到格子x=i的情况来说

• 如果格子上及左边的棋子数<格子右边的棋子数，那么x再向右移动，总步数会增加
• 如果格子上及左边的棋子数>格子右边的棋子数，那么x再向右移动，总步数会减少
• 如果格子上及左边的棋子数=格子右边的棋子数，那么x再向右移动，总步数不会变

3）从规律1）2）得到左右棋子数一样多的格子是总步数最少的，那么这些最小步数的格子是在一个区间内，并且区间的两端肯定是棋子所在的位置，才会造成区间外，格子左右棋子数不一致。

结论：在棋子所在位置得到的k个棋子移到到这个位置的最小操作数就是全局最小的，即聚合点的x坐标必然是给出棋子的x坐标之一。同理聚合点的y坐标必然是给出棋子的y坐标之一。所以只要在棋子所在位置找出聚合的最小操作数就是全局最小的操作数。

解题思路步骤：
1）求k个棋子移动到格子A的最小操作次数：先求所有棋子到格子A的曼哈顿距离，由于需要k个棋子，所以找到所有棋子中离格子A最近的k个棋子，它们的曼哈顿距离之和就是移k个棋子到格子A的最少操作次数。
2）循环所有棋子所占的格子，根据步骤1）求到移k个棋子到这个格子的最小操作次数，那么所有棋子所占格子中最小的操作数，就是题目所要求的最小操作数。

#include<iostream>
#include<algorithm>

using namespace std;

int n;
vector<int> x(55);
vector<int> y(55);
vector<int> ans(55);

void calculate(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int dis[n],tmp=0;
            //计算曼哈顿距离
            for(int k=0;k<n;k++) dis[k] = abs(x[i]-x[k]) + abs(y[j]-y[k]);
            sort(dis,dis+n);
            for(int k=0;k<n;k++){
                tmp+=dis[k];
                ans[k] = ans[k]>tmp ? tmp : ans[k];
            }
        }
    }
}
int main(){
    cin>>n;

    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<n;i++) cin>>y[i];
    for(int i=0;i<n;i++) ans[i] = 10000000000;

    calculate();

    for(int i=0;i<n;i++){
        cout<<ans[i];
        if(i<n-1){
            cout<<" ";
        }
    }
    return 0;
}

方法二：