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

[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，就是[不考虑花束数量均摊]的最小值。

 

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

 

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