实际问题是这样的:
麦当劳计划在一条直道上开辟一些关节(比方说n).这些接头需要仓库来存放食物.仓库可以存储任意数量的关节的食物,但必须仅位于其中一个关节.McD拥有数量有限的仓库(比如k),并希望将它们放置在最小化距离最近仓库的平均距离的位置.
给定关节坐标的数组(n个元素)和整数'k',返回一个'k'元素数组,给出仓库最佳定位的坐标.
对不起,我没有任何可用的例子,因为我是从记忆中写下来的.无论如何,一个样本可能是:
array = {1,3,4,5,7,7,8,10,11}(n = 9)
k = 1
答案:{7}
这就是我一直在想的:对于k = 1,我们可以简单地找出集合的中位数,这将给出仓库的最佳位置.但是,对于k> 1,给定集合应分为"k"子集(不相交,以及超集的连续元素),每个子集的中位数将给出仓库位置.但是,我不明白应该在什么基础上形成'k'子集.提前致谢.
编辑:这个问题还有一个变化:取代sum/avg,最小化一个关节和它最近的仓库之间的最大距离.我也没有得到这个..
有一个矩形的硬币网格,其中头部由值1表示,尾部由值0表示.您使用2D整数数组表(1到10行/列,包括1和10行)来表示.
在每次移动中,您选择网格中的任何单个单元格(R,C)(第R行,第C列)并翻转所有单元格中的硬币(r,c),其中r介于0和R之间,包括,c介于0和C之间,包括0和C. 翻转硬币意味着将单元格的值从零反转为一或一到零.
返回将网格中的所有单元格更改为尾部所需的最小移动次数.这将永远是可能的.
例子:
1111
1111
returns: 1
01
01
returns: 2
010101011010000101010101
returns: 20
000
000
001
011
returns: 6
这就是我所尝试的:由于翻转的顺序并不重要,并且两次移动硬币就像完全没有移动一样,我们可以找到翻转硬币的所有不同组合,并最小化硬币的大小组合(意思是那些给出所有尾巴的组合).
这可以通过制作一个由所有硬币组成的集合来完成,每个硬币由一个索引表示.(即如果总共有20个硬币,这个集合将包含20个元素,给它们索引1到20).然后制作所有可能的子集,看看它们中的哪一个给出答案(即,如果在子集中的硬币上移动给我们所有的尾巴).最后,最小化良好组合的大小.
我不知道我是否能够过于清楚地表达自己...如果你愿意,我会发一个代码.无论如何,这种方法太耗费时间和浪费,并且对于大于20的硬币(在我的代码中)是不可能的.怎么去这个？