最短距离问题
c++吧
全部回复
仅看楼主
level 12
QQ懒羊羊QQ 楼主
X轴上面有n（0<n<1000)个点，-10000<x<10000.....在x轴上面找一个点，使其到其他点的距离之和最小。
我想问的是如何根据这n个点来确定要找的点的范围，我用的是for(i=-10000;i<=10000;i++)
老师说不行，如何缩小范围[委屈]
2011年06月14日 12点06分 1
level 8
夜雨の离殇
hash，离散化
2011年06月14日 12点06分 2
level 8
夜雨の离殇
因为点是1000个所以离散化之后的复杂度是1000
如果像你那样就是20000，还没法解决小数问题
2011年06月14日 12点06分 3
level 12
QQ懒羊羊QQ 楼主
不懂。。。我测试的是30个点 是不是在15~16个数之间啊
2011年06月14日 12点06分 4
level 8
夜雨の离殇
[汗]神马跟神马……你没听懂我的意思啊
2011年06月14日 12点06分 5
level 12
QQ懒羊羊QQ 楼主
我取了30个点，n=30.。。。。。。。。。。不想从-10000~10000来循环 要径最大可能缩小范围
2011年06月14日 12点06分 6
level 12
QQ懒羊羊QQ 楼主
我还没学神马离散。。
2011年06月14日 12点06分 7
level 8
夜雨の离殇
[汗]行才怪
谁让你扫描坐标轴了
有几个点扫几个点不久行了
2011年06月14日 12点06分 8
level 15
幻の上帝
排序找中位数。要是偶数个就中间两个点的正中间。
小学奥数题。
[瞌睡]
2011年06月14日 12点06分 9
level 12
QQ懒羊羊QQ 楼主
2011年06月14日 12点06分 10
level 12
QQ懒羊羊QQ 楼主
原题如上
2011年06月14日 12点06分 11
level 12
QQ懒羊羊QQ 楼主
用分而治之 单独求x y 坐标
2011年06月14日 12点06分 12
level 8
夜雨の离殇
[撞墙至死]OI题
用n^2暴力就行
至于你的扫描坐标，累死你也不能过
2011年06月14日 12点06分 13
level 15
幻の上帝
二维曼哈顿么。递推+排序。
epic.yo2.cn/articles/post124.html
2011年06月14日 12点06分 14
level 12
QQ懒羊羊QQ 楼主
用n^2暴力就行[瀑布汗~]bu dong
2011年06月14日 12点06分 16
level 15
幻の上帝
只是一维情况……
2011年06月14日 12点06分 17
level 12
QQ懒羊羊QQ 楼主
那是错的吧[背扭]
2011年06月14日 12点06分 18
level 12
QQ懒羊羊QQ 楼主
把2维转化成2个一维的
2011年06月14日 12点06分 19
level 12
QQ懒羊羊QQ 楼主

x y 都独立的
2011年06月14日 12点06分 20
level 8
夜雨の离殇
[瞌睡]那是10^5的做法，题目才1000
写暴力比较容易
2011年06月14日 12点06分 21
1 2 3 4 尾页