HAUT1227 Flowers贪心

题目链接：haut1227

题面

解题思路

贪心

这个问题的第一个关键点在于要发现：组成混合颜色的方案一定要优先于组成纯色的方案。因为组成混色方案更具鲁棒性。在相同资源下，组成三束分别不同颜色的花束一定也可以将其改成三束混合颜色的花束；而在小于三束混色花束的资源下却无法组成任何一束花。于是，我们大胆认为前者方案优于后者。

第二个关键点在于要发现：构成最大方案数的核心部分就是混合颜色的花束数量，因为当无法构成混合颜色花束时，问题就相当简单了，直接计算各自的纯色花束即可。而构成混合颜色花束数量取决于三种颜色中，花朵数量最小的那堆，所以我们先处理那堆最小的，处理完毕后再处理剩下的纯色的方案。

根据关键点二，我们容易形成一种错误的算法，就是把所有『最小堆』中的花朵全部都拿来构成混合颜色的花束，基于这个算法我们可以给出反例：2 7 7，这个样例正确答案应该是 5 ，也就是一个混合颜色花束加四束纯色花束，而不是上述算法所计算的 4 。

问题出在哪呢？这样的只形成局部最优而非全局最优的错误点不由得让人想直接去搜索，但是怎么搜索呢？根据关键点一的观点，我们可以考虑搜索『最小堆』的混合花束数量（实际上枚举就行了）。但是如果『最小堆』的花朵数量很多，那么我们这块的复杂度是相当爆炸的。我们发现在这种搜索策略下，『最小堆』中花朵的状态仅有三种：用于纯色、用于混色、闲置。而根据关键点一，当它能用于纯色时我们显然可以将其用混色替代。于是，状态就变成两种：混色、闲置。显然，当闲置了三个花朵我们肯定能将其至少组成一个纯色花束（其实还是可以转成混合颜色花束）。于是，这堆中，闲置花朵数量仅需考虑 $012$ ，最后取三种方案中最大的即可。

最后，我们再考虑『最大堆』『次大堆』剩下的花朵组成纯色花束。事实上，我们优先考虑混合颜色花束相当于是在切断三种颜色之间的相互约束，使得问题更简单而已。

可能我们还有个疑问，就是『最小堆』中最优情况下，那些闲置的花朵会不会有机会和其他颜色的花朵再构成混合花束？答案是否定的。因为我们枚举的这个最优情况实际上就是在最大程度利用其他两堆，使其能够减少闲置，更多地利用起来形成纯色花束，也就是说，最优情况下，其他两堆必然至少有一堆剩下的花朵全部都能构成纯色花束。

时间复杂度：$O(1)$ ，空间复杂度：$O(1)$

实现代码

贪心

#include <bits/stdc  .h>

using namespace std;

int f(int r, int g, int b) {
    int m = min({r, g, b}), k = 0;
    for (int i = 0; i <= min(m, 2); i  ) {
        k = max(k, m-i   (r-m i)/3   (g-m i)/3   (b-m i)/3); //混合颜色   纯色
    }
    return k;
}

int main() {
    int red, green, blue;
    cin >> red >> green >> blue;
    cout << f(red, green, blue) << endl;
    return 0;
}

这篇好文章是转载于：学新通技术网