📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3360| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

google: Find the best meeting point

全局:

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

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

x
there is a town which is a square grid.. every point can be reached from any other point..
there are N people in the grid.. find a common meeting
ground for them such that the total distance traveled by those 10 people are the least..

补充:
就是一个尔维矩阵, 各个点只能横着走和竖着走. meeting place指一个单元block,对应于二位数组的一个坐标

上一篇:寻找二进制1的个数相同的相邻数
下一篇:交换奇偶bit
🔗
 楼主| wwwyhx 2011-7-15 15:58:29 | 只看该作者
全局:
简化问题,如果是一维数组怎么做,如果n=2怎么做,n=3怎么做....
啊,答案就是median

  1. struct POS
  2. {
  3.         int x;
  4.         int y;
  5. };

  6. bool CompX(POS a, POS b) { return a.x < b.x; }
  7. bool CompY(POS a, POS b) { return a.y < b.y; }

  8. POS FindMeetingPlace(POS a[], int n)
  9. {
  10.         assert(a && n>0);

  11.         POS pos;
  12.         sort(a, a+n, CompX);
  13.         pos.x = a[n/2].x;

  14.         sort(a, a+n, CompY);
  15.         pos.y = a[n/2].y;

  16.         return pos;
  17. }
复制代码
回复

使用道具 举报

🔗
lklk1986fa 2012-2-17 11:27:51 | 只看该作者
全局:
今天电面考到这道题了,可惜我没答上来,早点看到就好了,我只想到把grid divide 成 half, 分别求 min,然后再combine, 有点像merge sort。interviwer想要的结果是 N个people 横向 映射到一维数组,求最小 点(1,n), 纵向映射到一维数组求最小(m,1), 那么(m,n)就是最小meeting point, PS: people 可以重叠。
回复

使用道具 举报

🔗
0864 2012-3-27 16:28:17 | 只看该作者
全局:
感觉上面两位的题是不是有出入。。。因为只能横走和竖走,所以可以拆分为x,y来做。不错的思路。
回复

使用道具 举报

🔗
gboystal 2012-7-28 11:17:01 | 只看该作者
全局:
wwwyhx 发表于 2011-7-15 15:58
简化问题,如果是一维数组怎么做,如果n=2怎么做,n=3怎么做....
啊,答案就是median

谁能从数学上证明。。没想出来
回复

使用道具 举报

🔗
liu.hit 2012-7-31 11:18:21 | 只看该作者
全局:
gboystal 发表于 2012-7-28 11:17
谁能从数学上证明。。没想出来

一维情况下,考虑用归纳方法证明
一个人,不用走
两个人,到两人之间的任何位置汇合都可以
三个人,拆分成左右两人和中间一人,则中间人的位置为汇合点
四个人,拆分成外侧两人和内侧两人两个组,取两组人汇合点的交集,即内侧两人之间的任何位置
5人、6人...
依此类推,可以得到结论,对总人数n:
1) 为奇数时,汇合点为中间人所在点
2) 为偶数时,汇合点为中间两人之间的任何位置

多维情况下,因各维度正交独立,
可参照板凳同学方法求得各维度的汇合点,然后综合得到多维情况下的汇合点
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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