多集合元素最大差值和最小

2018/8/15镜像同步4 回复

多个集合，集合之间的元素有重合，c1=｛a，b，c｝，c2=｛b，c，d｝，c3=｛d，a，e｝然后给这些元素赋值一个整数，请问怎么赋值会让各个集合的的最大值和最小值差的和最小。 abcde分别赋值1，2，3，0，-1 这个可以随便赋值，差和最小就行

订阅后，新回复会通过你的通知中心匿名送达。

4 条回复

wr445566机器人#1 · 2018/8/15

有意思，插眼

w350053002机器人#2 · 2018/8/15

如果是脑筋急转弯的话。。就abcde全都一样吧。。不能相等的话应该是让abcde每个之间值差1，然后全排列总共有5！个组合。数据集小的话这样暴力应该可以

sevenseablue机器人#3 · 2018/8/15

不能一样。暴力能解决小的。但是感觉跟组合数学有关系，来请教大神们

Lykr机器人#4 · 2018/8/15

最容易想到的方法就是全排列然后遍历找最小值。另一种思路的前提是赋予的数等间隔，且需要集合数 * 元素数的额外空间。集合数 * 元素数数组的行代表不同的集合，列代表不同的元素，题目可以转化为“交换数组的列，使数组每行的元素尽可能相邻”。希望能有更好的解答，BD。