首页 > 试题广场 >

堆棋子

[编程题]堆棋子
  • 热度指数：15180 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易将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
算法知识视频讲解
开通博客
头像 诗云panther
发表于 2021-08-20 12:37:02
include include using namespace std; int n , x[55] , y[55] , ans[55];void helper(); int main(){ cin>>n; for(int i=0;i<n;i++) cin>>x[ 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 杨先森1
发表于 2020-04-10 22:41:21
可以明确的是，所有备选格子的坐标必然在 x[]和y[]选取，优先可以计算出所有点到所有备选格子的距离，然后进行排序，使用前缀和可以快速取出每个备选格子包含不同棋子数的距离之和。最后取最小值即可。时间复杂度 O(n^3logn)空间复杂度 O(n) #include <stdio.h> # 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客题解官
发表于 2020-06-05 17:50:28
题解 难度：中等 知识点：暴力求解 棋子只能上下左右移动，所以移动的步数即操作次数为两个位置的曼哈顿距离坐标(x1,y1)的i点与坐标(x2,y2)的j点的曼哈顿距离为d(i,j)=|x1-x2|+|y1-y2| 本题是要求解棋盘上出现一个格子中至少k个棋子的最少操作。那这k个棋子出现在那个格子呢， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-20 15:15:26
解题思路 这是一个最小曼哈顿距离的问题。对于每个目标位置 ，我们需要计算将 个棋子移动到该位置所需的最小步数。 对于每个目标位置，我们计算所有棋子到该位置的曼哈顿距离。 将距离排序后，取前 个距离之和，即为将 个棋子移动到该位置所需的步数。 遍历所有可能的目标位置，更新每个 的最小步数。 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 模拟 网易 2018 Java工程师
来自：网易2018校招内推编...
上传者：小小
难度：
61条回答 20734浏览

热门推荐

通过挑战的用户

查看代码

相关试题

堆棋子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号