一个王国的公平分裂

Question

最近,我参加了编程比赛.有一个问题,我仍然在考虑.编程语言并不重要,但我用C++编写.任务是这样的:

如您所知,Flatland位于飞机上.Flatland有n个城市,其中i个城市位于(xi,yi)点.有AI的公民居住在第i个城市.平地之王决定将王国分配给他的两个儿子.他想以无限直线的形式建造一堵墙; 每个部分将由其中一个儿子统治.墙不能穿过任何城市.为了避免兄弟之间的嫉妒,两部分的人口必须尽可能接近; 正式地,如果a和b分别是居住在第一和第二部分城市的公民总数,则| a - b |的值.必须尽量减少.帮助国王找到最佳分工.城市数量小于1000.所有坐标都是整数.算法的输出应该是最小| ab |的整数

好吧,如果我知道线的方向,那将是非常简单的任务 - 二进制搜索:

我不想要代码,我想要想法,因为我没有.如果我抓住了想法,我可以编写代码!

我不知道最佳方向,但我认为它可以以某种方式找到.那可以找到它还是以其他方式解决这个问题？

水平/垂直线不是最佳的示例:

1

\
 \
2 \      1

Answer 1

安萨兹

蛮力方法是检查所有可能的分裂......

首先应该注意,线的确切方向无关紧要.它总是可以少量移动,并且有一些案例的最小值不止一个.什么重要的城市到哪个城市的哪个方面.即使只是尝试所有这些可能的组合,找到它们也并非易事.为此,我提出以下算法:

如何找到所有可能的部门

• 对于每对城市x和y,连接它们的线将王国划分为"左"和"右".然后考虑left,right,x和y的所有可能组合:

  • left + x + y vs right(C)
  • left + xvs right + y(A)
  • left + yvs right + x(D)
  • leftvs right + x + y(B)

实际上我并不是百分百肯定,但我认为通过这种方式你可以找到所有可能的分裂,并进行有限数量的试验.由于城市没有大小(我假设半径为0),连接x和y的线可以稍微移动,以包括在其中任何一侧的任一城市.

这个简单方法肯定会失败的一个反例是超过2个城市在一条直线上

例

这张照片说明了我的上述算法的一步来自OP的例子.x和y是拥有1个居民的两个城市.实际上,在这对城市中,已经有了所有可能的分歧.(无论如何,3分是微不足道的,因为对于什么组合是没有几何限制的.有趣的是,从4点开始它们在飞机上的位置确实很重要.)

Colinear点

经过一些讨论和富有成效的评论后,我得出结论,共线点并不是真正的问题.在评估4个可能的划分(每对点)时,只需要考虑这些要点.例如,假设在上面的例子中是(-1,2)处的另一个点.然后,这一点将位于A和C的左侧,B和D的右侧.