2023级算法E3练习赛

2023级算法第三次上级赛

A 2024-小水懒和蓝园

思路分析

题目需要求得最少的快递数，能够将所有花全部发往学院路。这里发现题目具有贪心的属性。

假设每次都必然会送走一束最轻的花，这个假设可以成立，因为最终所有花都会被送走，只是送走的先后顺序问题。

那么很容易知道，使得快递数能够最少的方案就是让这束最轻的花带上此时最重的能带走的花。并且如果此时所有花中最重的花不能够被一同带走，那么这朵花一定只能被单独送走，于是可以在每一轮送快递时，将不能连同最轻花一同带走的当前最重的花单独先送走，直到剩下的花中最轻最重的能一同带走，此时将这两朵花打包送走，进入下一轮，重复直至全部花都送走，那么此时累计的快递数总数是最少的。

B mjh的淘宝店

思路分析

如果没有优惠制度的话，那么很容易知道这是一个经典的背包问题，但是现在的问题是，它存在优惠制度了。

所以可以考虑，从最简单的情况开始想，如果在k为0的基础上，求k=1的情况要怎么做。

可以考虑在此时的购物清单中，将最贵的一个物品免费，然后买剩下的物品，或者将剩下的物品中价值最高的一个物品免费，然后放进已购物清单内。也许这两种情况具有一定的包含关系，并不互斥，我们想使它互斥。

其中前一种情况下不能保证最后获得的价值一定比后一种高，所以这两种情况存在一个最优解。

是否可以直接考虑k的情况