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

问一道没见过的题目

🔗
koga | 只看该作者 |倒序浏览
全局:

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

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

x
given List<(x,y,val)>和 int D ,其中x,y 是平面一点的坐标,val是这个坐标的值,也就是给了平面上一些点和这些点附带的值, D是一个数,
找出平面上一点 (a,b) such that sum(val_1/S_1+val_2/S_2+... val_k/S_k) is maximum, where val_i is the val associated with point (x_i,y_i),S_i is the euclidean distance from (x_i, y_i) to (a, b) + 1, and S_i <= D  
这题有什么思路

上一篇:梦想还是要有的,万一实现了呢!你说是吧?
下一篇:开一个刷题贴,以后多刷题
全局:
感觉是类似重心, 或者是权重.

这里你说的k, 我假设是所有的点..

最后求的答案是一个圆心, 使得它包含所有的点, 并且满足到最大的那个公式. D代表半径.

直觉应该是[先证明5点共圆] 咦?

可能是类似graham scan这样在最外面的点上做圆, 找intersection.. 然后在intersection 里面找点..

好像跟weight没什么关系了.?

{:8_249:}


补充内容 (2018-9-14 00:16):
虽然写的是L2距离, 其实算L2方就够了, 不用sqrt. 这样跟曼哈顿距离其实基本差不多.

找圆/方内的所有点的话, 就找[x-d, y-d] 到 [x+d, y+d]上所有的点吧.. 这样
回复

使用道具 举报

🔗
 楼主| koga 2018-9-15 03:54:42 | 只看该作者
全局:
肥宅快乐水 发表于 2018-9-14 00:13
感觉是类似重心, 或者是权重.

这里你说的k, 我假设是所有的点..

这样还是brutal force, N^4复杂度
回复

使用道具 举报

全局:
koga 发表于 2018-9-15 03:54
这样还是brutal force, N^4复杂度

好像有点道理.

我又想了一下, 如果是1d的情况, 那应该就是求最重的点.. 或者是top重的点

直觉上应该是按重量排序的点.. 但是我没办法证明这个greedy



回复

使用道具 举报

🔗
 楼主| koga 2018-9-15 04:33:13 | 只看该作者
全局:
肥宅快乐水 发表于 2018-9-15 04:24
好像有点道理.

我又想了一下, 如果是1d的情况, 那应该就是求最重的点.. 或者是top重的点

应该不只是重量
还有D这个参数,两个圆,一个里面单个val is higher, 但另一个里面点多,就没法算
回复

使用道具 举报

全局:
koga 发表于 2018-9-15 04:33
应该不只是重量
还有D这个参数,两个圆,一个里面单个val is higher, 但另一个里面点多,就没法算

这D到底干嘛用的,如果最远的点距离超过2D这题怎么做
回复

使用道具 举报

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

本版积分规则

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