娱乐 【红包inside！】萌新的算法挑战#3~

[伽莫夫博士]

能不能提供个示例输出？

“每个花束中的花品种颜色各不相同”指的是（品种不同颜色也不同）还是（品种不同或颜色不同）？

[旺旺先辈]

我的理解1,2结合起来就成了，每束花中每种每色花的个数为0或1？不知道有没有偏差，最好还是有个示例解呢

[Refrain]

现在是无限花之循环23333

[yuibingyzy3]

做什么数学题，这钟事情交给骰娘就好了吗

[gaia10086]

谜题过于难，脑子已经烧坏

[谷fds]

一共520朵花，n : 花的品种的个数，c: 花的颜色的个数。要求：每个花束中的花数量差值不可超过一

 每个花束中的花品种颜色各不相同          你想要将这些花放在尽可能少的花束之中
解：难点为花束要少，即每束花花量最多，假设520朵都放一束里，n=520，c=1。
答：有520朵不同品种的花，每个品种花都只有一种颜色，颜色有520种。（色值问题其实没有完全一样的颜色）
自定义框架下：常用的十二种颜色分别是红，橙，黄，绿，青，蓝，紫，灰，粉，黑，白，棕。 十二色又称十二色环 即0<c<13,0<n<521。品种颜色各不相同即同颜色只能出现在一个品种上，要求每束花里品种不同即一束花最多有12朵颜色的品种不同花。即最少1束花，一束花里 43 43 43 43 43 43 43 43 4 44 44 44 44 差值为1 也满足，总520朵

[无棉乐园]

算不出来，我选择直接送菜花，完美

[让我们向盟约起誓]

束缚条件给的不是很清晰，仅仅凭借我大学概统水平不能看出这是怎么回事，太菜了

[playerzhou]

没看懂题目啥意思，有没有样例输出和解读呀

[lang20006059]

“简单轻松”！！！

[Muriya Tensei]

好难啊，不会

能想到的思路1是二分答案+dfs的check，但是好像答案因为有差值1的约束，并不具有单调性

思路2是试图转化为二分图，想不懂，大概是只能处理min(c,n)== 2的情况

最后就是枚举size+dfs回溯了。总感觉问题是npc的，但又不会证明或者规约

 

（我说实话，就算数据量很小，指数级dfs回溯都不一定会写，好讨厌带约束的最值

这题我如果遇到，我就直接模拟退火了，生死由命成败在天

[mhs117]

不是太能理解做法，如果是每个种类的花束中以种类划分花的颜色尽可能多而且差值均等那试试看贪心算法？

先选定某个品种的某个颜色，最大值定为temp，然后比对其他颜色的最大值，如果差值小于1则不动，大于1则取这个值赋给temp依次类推直到得到所有种类的temp

不过这样不太像贪心了

[cerbbq]

面对压根不懂的编程，极端唯心摸摸掏出了天神裁决巨像

[drop_table_all]

 

首先将每朵花转换为另一个矩阵：（其实我是想起了消消乐）

如：

引用

1, 2, 3, 1, 1

0, 1, 0, 1, 1

中，红色数字的花朵转为：

引用

1 1 1 2 1

0 0 0 1 0

则可以轻易得出，对于任意一束花：

"其所有花的foo矩阵求和结果中的每一个值都不大于2" 等价于 "该花束满足题目条件"；

证明如下：

剧透

正向：如果花束有冲突，则冲突花位置的值肯定不小于 3；

反向：如果花束满足条件，但 某点的值>=3 则：

  1. 该点有花，但因为满足条件，同行或同列没有花，此点的值为 2；

  2. 该点没花，则[所在行]和[所在列]的花朵数量之和>=3，则鸽笼原理，一定有一行/列有两朵花，矛盾。

 

因此我们将题设矩阵转为上文的矩阵，将其结果中最大值除以2，就是[不考虑花束数量均摊]的最小值。

 

（但是均摊算法还没想好，应该得矩阵排序下）

 

（说起来我想起那个红魔馆女仆打扫房间的矩阵题目了...）

[饿掉鱼]

思路:1.把每个种类中的颜色数量最多的花依次排序

2.依次把数量最多的这些花组成花束

3.最后会剩下有空缺种类颜色的,从之前的花束里遍历,如果其中有自己空缺的种类+颜色且花束为满,摘到自己的花束中,直到自己花束花的数量=最多的花束-1

[pollutionsoul]

数学始终徘徊在及格线的跪了

[独望星空]

乐。我决定遇到困难摆大烂！