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

[AlGoRiThM]

哈喽大家好，我又来了~

电脑坏了半个月，无聊死我了QAQ，想必大家十分思念我吧！

所以，当当当，我给大家带来了第三期的算法挑战！

这一次的算法挑战是快快乐乐的约束编程！简单轻松简单轻松~

题目如下：

引用

Kris麻麻生气了！因为你在上一次520没有给他送花！

你有520朵花束，这些花束中有着多个品种和多种颜色，作为一名计算机科学家，你将这些花束进行编号

最终，你获得了以下输入：

n : 花的品种的个数

c: 花的颜色的个数

从这个输入往下，则是每一朵花的颜色的数目

例如：

2

5

1, 2, 3, 1, 1

0, 1, 0, 1, 1

在以上输入之中，

第一行第二行代表花的颜色品种个数

第三行为品种一的花有着一朵颜色A, 两朵颜色B, 三朵颜色C, 一朵颜色D和一朵颜色E的花

以此类推， 第二行意味着品种二没有颜色为A，C的花，但是有颜色B, D, E的花各一朵

引用

你想要按照以下规则给Kris麻麻送花：

1. 每个花束中的花数量差值不可超过一

2. 每个花束中的花品种颜色各不相同

3. 你想要将这些花放在尽可能少的花束之中

请问，你打算采用什么方法来给Kris麻麻送花呢？

 

七月 20, 2022，由AlGoRiThM修改

[久帝]

4 小时前，AlGoRiThM说道:

请问，你打算采用什么方法来给Kris麻麻送花呢？

用直升机撒花

这种时候还管什么数学2333

[白龙与马难以兼得]

只买一朵花，一种品种一种颜色，那不就解决了，那么问题来了，为什么不尽可能多买点?

答

：没钱

[AlGoRiThM]

6 小时前，白龙与马难以兼得说道:

只买一朵花，一种品种一种颜色，那不就解决了，那么问题来了，为什么不尽可能多买点?

答

：没钱

但是要有尽可能少的花束啊233

[AlGoRiThM]

所以说，回复大家要点开看啊0.0有约束条件的啊！

七月 6, 2022，由AlGoRiThM修改

[AlGoRiThM]

于 2022/7/5 于 AM4点04分，久帝说道:

用直升机撒花

这种时候还管什么数学2333

噢！好欸

撒花！

Kris看了会流泪！

七月 6, 2022，由AlGoRiThM修改

[syd]

没太理解题目条件……

于 2022/7/5 于 AM6点27分，AlGoRiThM说道:

2

5

1, 2, 3, 1, 1

0, 1, 0, 1, 1

所以这些是输入，但又是从

于 2022/7/5 于 AM6点27分，AlGoRiThM说道:

你有520朵花束，这些花束中有着多个品种和多种颜色，作为一名计算机科学家，你将这些花束进行编号

统计来的，也就是说

n  // 个品种
c  // 种颜色
第一个品种的颜色映射数组  // 数组长度 == 所有颜色种数
……
第 n 个品种的颜色映射数组

这些全是输入，而用户输入是能够保证「映射数组里的总数合计 == 520」对吗？

[AlGoRiThM]

6 小时前，syd说道:

没太理解题目条件……

所以这些是输入，但又是从

统计来的，也就是说

n  // 个品种
c  // 种颜色
第一个品种的颜色映射数组  // 数组长度 == 所有颜色种数
……
第 n 个品种的颜色映射数组

这些全是输入，而用户输入是能够保证「映射数组里的总数合计 == 520」对吗？

520只是为了取悦Kris麻麻，这道题和520没有任何关系XD

想得到的算法只是一个通过输入获得一个相对平均的最佳分配输出，也就是做到题目里面给出的约束条件就可以了

最后的答案可以是个模型，也可以是单纯的算法描述~有什么不明白的可以继续讨论，因为这个题是纯粹自己编的，可能会出现什么bug也不一定？

[syd]

10 分钟前，AlGoRiThM说道:

520只是为了取悦Kris麻麻，这道题和520没有任何关系XD

想得到的算法只是一个通过输入获得一个相对平均的最佳分配输出，也就是做到题目里面给出的约束条件就可以了

最后的答案可以是个模型，也可以是单纯的算法描述~有什么不明白的可以继续讨论，因为这个题是纯粹自己编的，可能会出现什么bug也不一定？

（放弃思考

蹲一个大佬讲思路

[猛男鸽王]

还不错嘛～～

让人回忆起了当年做NOI的过往……

七月 8, 2022，由猛男鸽王修改

[Highfrog HUO]

简单轻松简单轻松是吧

[dhsshh]

为什么我都上sstm还要做题啊喂！

是工作不饱和，还是学习太轻松，我现在只想舒服躺平

[killhunter1]

直接撒花

[響可可]

拉一车怼到到脸上

[yyh]

于 2022/7/7 于 PM4点48分，AlGoRiThM说道:

520只是为了取悦Kris麻麻，这道题和520没有任何关系XD

想得到的算法只是一个通过输入获得一个相对平均的最佳分配输出，也就是做到题目里面给出的约束条件就可以了

最后的答案可以是个模型，也可以是单纯的算法描述~有什么不明白的可以继续讨论，因为这个题是纯粹自己编的，可能会出现什么bug也不一定？

那也就是说不一定非得得到最优解是吗？只是尽量满足给的约束条件就行？

虽然我不太会证明，但是我凭感觉推断这个问题好像是个NP难问题啊

在不要求最优解的情况下可以用一些启发式的算法，比如遗传算法和邻域搜索之类的，要最优解嘛.....emmm好吧我其实不太知道最优解怎么求

 

[zhuyg123]

表示大佬的谜题过于难，脑子已经烧坏了

[及時雨]

數學不好的我看得是一知半解!!

[jjjjkkkkkk3232]

可以直接直接删库跑路吗

[peirehui]

为什么这里还会有编程题，刚刚才痛苦过

[骚男]

10 小时前，及時雨说道:

數學不好的我看得是一知半解!!

有没有可能数学和算法思维还是有差距的

8 小时前，jjjjkkkkkk3232说道:

可以直接直接删库跑路吗

这种题还不至于……

2 小时前，peirehui说道:

为什么这里还会有编程题，刚刚才痛苦过

刚刚，阁下有在学计算机语言？

[弧光]

第二个约束优先级最高，其余的感觉就贪心找最优解吧，暂时想不出来，看题目种类和颜色其实是一样的属性，个人想法就是取种类颜色最小值为每一束花的个数，从种类或者颜色数量最多的花开始拿

 

七月 17, 2022，由弧光修改

[抹消思绪]

约束1和3的优先级如何呢。

例如说，解A包含3个花束，size分别是10、9、1；解B包含4个花束，size分别是5、5、5、5。

这种情况下哪个是更好的解？

[冷枫月雨]

还是速速删库跑路吧

[AlGoRiThM]

于 2022/7/19 于 PM4点42分，抹消思绪说道:

约束1和3的优先级如何呢。

例如说，解A包含3个花束，size分别是10、9、1；解B包含4个花束，size分别是5、5、5、5。

这种情况下哪个是更好的解？

啊，出现了Bug了XD，这就去改一改

[抹消思绪]

4 小时前，AlGoRiThM说道:

啊，出现了Bug了XD，这就去改一改

好像能做了，但是我选择开摆。