Question

求这题的思路!

某条路长达100000米,道路沿线分布有成千上万个居民点,大道可以看成一条线段,左端为起点,标记为0.右端为终点,标记为100000.沿线的居民点可以用线段上的点表示.每个点标上一个整数,表示该点到线段左端点的距离.请在这条线段中找出一个点,从这个点到每个居民点的距离之和最小.
用户输入n个数字(1<=n<=100000).这些数字表示各个居民点.(它们并未排序).每个数字都不超过100000.输出从这个点到每个居民点距离之和.

主要是数组不能定义上50000...不然排序都解好了....
有高手没?
我只要思路,不要源码...

Answer 1

如果是偶数个点,那么应该建造在最中间的两个点之间
如果是奇数个点,那么应该建造在最中间的点
不过好象要排序
哎...
排序后
如果是偶数个点,那么把较大的一半减教小的一半
如果是奇数个点,则忽略最中间的点,其他的同上

Answer 2

我想可以把这么多数据存到文件或数据库里再进行处理说不定可以,以前在书上貌似看到过类似的东西,我只想到这么些

Answer 3

duo zuojici

Answer 4

你应该到数学方面问，以前上学的时候，有个同学做过一个和这个类似的高数建模。记着好像很难。

Answer 5

50000~50001 最接近这个数的点就是结果