一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 492|回复: 7
收起左侧

[高频题] OA遇到的一个题目 毫无头绪 求大佬帮忙看看

[复制链接] |只看干货 |高频题, 刷题
我的人缘0

升级   70%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
给定一个m*n的矩阵 指定可以在任意位置里填k个0  以填0格为中心  其它的格子的数字为距离任意中心的距离 优先取最小
要求在把0填入到矩阵中后 使矩阵里的最大数字达到尽可能的最小  函数返回值为这个最大数字的值

例如  m=4, n =4, k =3
则可选最优解为
1 0 1 1
2 1 1 0
2 1 2 1
1 0 1 1

函数返回2

评分

参与人数 1大米 +10 收起 理由
14417335 + 10

查看全部评分


上一篇:Remove brackets from an algebraic string 问题
下一篇:Career Cup Top 150 Questions
我的人缘0

升级   1.71%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (31)
 
 
0% (0)    👎
这道题是building office,roblox的oa里出现过,也在mathwork的oa里出现过。oa对时间复杂度的要求卡得不是很紧,通用做法是dfs枚举每一种摆放0的摆法,然后对每种摆法以每个0为起点bfs得到最大距离。时间复杂度大概是O(n^3)的样子,估计值可能不准确。
回复

使用道具 举报

我的人缘0

升级   95.43%

swsyhhy 2020-9-19 11:16:35 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (102)
 
 
2% (3)    👎
本帖最后由 swsyhhy 于 2020-9-19 11:34 编辑

一个不靠谱的猜测

1. 二分答案(这步应该是靠谱的),假设现在的答案是mid
2. 贪心地去验证,是我,我就bfs地去填,bfs扫过的距离是2*mid(为啥是2*mid,就是理论上最长应该是0,1,2,1,0这种结构,从第一个0到第二个0的曼哈顿距离就是2*mid)
    然后在扫过的第一个边缘位置放一个0,这里放了0之后,其他边缘就不用管了。   
(这里还有一个怎么维护bfs队列的点,就是把上一次填0的所有>mid的点,再次入队)
    以此类推,最高添加k次0
    如果能够成功覆盖,就是二分low bound向上取mid;
    不能成功覆盖,就二分up bound向下取mid
3. 二分返回后,取low bound为答案

之所以说这个贪心不靠谱,是因为我就YY了一下,虽然我感觉好像还行,但是没有验证过
举一个5X5,k=3的例子
开始二分,L=1,R=5
mid = 3,验证的过程如下

0 1 2 3 4
1 2 3 4 5
2 3 4 5 N
3 4 5 N N
4 5 X N N

0 1 2 3 4
1 2 3 4 5
2 3 2 3 X
3 2 1 2 3
2 1 0 1 2

0 1 2 3 2
1 2 3 2 1
2 3 2 1 0
3 2 1 2 1
2 1 0 1 2

然后发现3可以,然后2不行
0 1 2 3 N
1 2 3 N N
2 3 N N N
3 N N N N
X N N N N

0 1 2 3 N
1 2 3 N N
2 3 X N N
1 2 3 N N
0 1 2 3 N

0 1 2 3 N
1 2 1 2 N
2 1 0 1 2
1 2 1 2 N
0 1 2 3 N

最后就是3了




评分

参与人数 1大米 +10 收起 理由
14417335 + 10

查看全部评分

回复

使用道具 举报

我的人缘0

升级   26.71%

meerkat 2020-9-19 11:37:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分

回复

使用道具 举报

我的人缘0

升级   78.86%

idealmaster 2020-9-19 14:51:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (295)
 
 
1% (4)    👎
这题m*n <= 28, k <= 5,可以尝试每个k点组合的最短距离,最多28C5次bfs

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分

回复

使用道具 举报

我的人缘0

升级   78.86%

idealmaster 2020-9-19 14:55:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (295)
 
 
1% (4)    👎
swsyhhy 发表于 2020-9-19 11:16
一个不靠谱的猜测

1. 二分答案(这步应该是靠谱的),假设现在的答案是mid

第一个0的位置很难判断,比如5*1,k=1,第一个0就不是左上角

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分

回复

使用道具 举报

我的人缘0

升级   95.43%

swsyhhy 2020-9-20 04:18:10 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (102)
 
 
2% (3)    👎
idealmaster 发表于 2020-9-19 14:55
第一个0的位置很难判断,比如5*1,k=1,第一个0就不是左上角

感觉你说的是对的...
如果M*N不是很大的话,其实就可以枚举起始点?
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| 猫与影子 2020-9-20 20:15:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
感谢各位大佬 没想到直接枚举是可以的 我以为时间复杂度会通不过  要是当时头铁直接写下去就好了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表