山工艺2018山东校考题校招可以内推吗？已经开始了吗

来源：蜘蛛抓取(WebSpider) 时间：2017-08-21 06:35 标签： 2020年校考院校名单

小易将n个棋子摆放在一张无限大嘚棋盘上第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子

每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知

道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.

输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数

输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割行末无空格

对于1个棋子: 不需要操作

對于2个棋子: 将前两个棋子放在(1, 1)中

对于3个棋子: 将前三个棋子放在(2, 1)中

对于4个棋子: 将所有棋子都放在(3, 1)中


 * 如上图 红色包围区域为需要计算点的范围

 * 修改了内存占用之后，时间又超标 

 * 后来在牛客网看到了@蟹粉馅大糖包  的分析：

 * “暴力枚举法居然过了，关键在于最后堆棋子的那个格孓，横纵坐标必然在棋子初始的横纵坐

用反证法xy轴其实是独立的，先只考虑x坐标假设把k个棋子堆到x0格子所用的步骤最少，

a个棋子初始茬x0的左边b个棋子初始在x0的右边，且a>b,那么必然存在横坐标为x0-1的格

子这k个棋子到x0-1的步数会更少，b>a的情况那么x0+1的目标将比x0更优，至于a=b

x0-1 和x0嘚步数是一样的。因此最终汇聚棋子的x坐标只要在棋子初始的x个坐标中考虑”

所以，只需要计算如下图红色线的交叉点距离所有棋子的距离

// 对排序好的临时数组求前k项和，即是点(xArr[i],yArr[j])到最近k个棋子的距离 // 也就是把k个棋子移动到该点所需要的最少步数。 // 将最少步数和结果数組的相应位置比较如果比他小，则将最少步数赋给结果数组相应位置

需要内推的同学请发简历到邮箱：

邮件名称格式（各项必填）：

  • 【姓名】-【岗位】-【学校】-【手机号】-【注明投递虎牙】

投完虎牙也可同时投YY哦扫下方二维码自选校园招聘职位投递即可~

大神们,请用你们的简历"羞辱我"
【社招】【百度】部门直推/公司内推各种岗位，实习看帖子最后
奇安信2020届春招补录继续岗位已更新，欢迎投递简历！

我要回帖

更多关于 2020年校考院校名单 的文章

 

随机推荐