堆棋子
题目
小易将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)中
示例1
输入
4 1 2 4 9 1 1 1 1输出
0 1 3 10
思路
最开始并没有做出来，在牛客网上听了左神讲解后才懂的。
-
一维情况：若干个点，一定是选择某聚合点，使得左右两边的点数相同时移动成本最小。奇数个点时肯定是中间点作为聚合点，偶数个点时一定是在中间两个点之间包括中问两个点。因此，得到结论：聚合点一定是若干个点中的某个点。
- 证明：一维轴上，若某点k左边有4个点，右边有6个点，所有10个点移动到点k的距离和为S。当k向右移动一个单位后，所有点移动到k的距离和为S - 6 + 4 = S - 2。继续右移直到k左右各5个点时，距离和达到最小值。只要k点两侧点数不平衡，向左或向右移就可以减小总距离和。因此聚合点一定是中间某个点或多个点，使得两侧的点数相等。
-
二维情况：若干个点，xy轴的移动成本是各自独立的，可直接分别求得聚合点的x坐标、y坐标，进而得到聚合点{x ,y }。但是结论同样成立：聚合点一定是在XY的笛卡尔积中。
-
如果只是求所有点移动到同一点的成本，那么可以直接求得聚合点的{x,y}坐标，进而得到总移动成本。但是现在需要求从1个点到N个点移动到同一点的成本，当1<n<N时，涉及到点的组合选择问题，所以我们在笛卡尔积中找最优解而不是直接求得指定点的最优聚合点坐标。
代码思路：
对N个点的x坐标和y坐标的所有组合，即N*N个聚合点，求每个聚合点到N个点的曼哈顿距离并push到优先队列中，依次从优先队列中取出top值，表示在当前聚合点下分别移动1-N个点时的最小移动成本，并更新解记录变量res[i]。最终res中的值即为分别移动1-N个点到某聚合点的最小成本。
代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
class Solution{
private:
int num_nodes;
vector<int> xcoors;
vector<int> ycoors;
vector<int> res;
private:
void init(){
cin>>num_nodes;
xcoors.resize(num_nodes);
ycoors.resize(num_nodes);
res.resize(num_nodes,INT_MAX);
for(int i=0;i<num_nodes;i++)
cin>>xcoors[i];
for(int i=0;i<num_nodes;i++)
cin>>ycoors[i];
}
void write_result(){
if(res.empty()==false)
cout<<res.front();
for(int i=1;i<num_nodes;i++)
cout<<" "<<res[i];
}
void calculate_result(){
for(int ix=0;ix<num_nodes;ix++){
int x=xcoors[ix];
for(int iy=0;iy<num_nodes;iy++){
int y=ycoors[iy];
update_result(x,y);
}
}
}
void update_result(int x,int y){
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<num_nodes;i++)
pq.push(abs(x-xcoors[i])+abs(y-ycoors[i]));
int sum=0;
for(int i=0;i<num_nodes;i++){
sum+=pq.top();
pq.pop();
if(sum<res[i])
res[i]=sum;
}
}
public:
void solve(){
init();
calculate_result();
write_result();
}
};
int main()
{
Solution s;
s.solve();
return 0;
}
