P7366 [CTSC2002] 月亮森林

· · 题解

题目大意：

小孩不懂事偷着出去玩获得了一个种子，这个种子有两个阶段，每当这个种子种下去生长的植物达到一个阶段他就可以获得一个种子，可以选择种下去或者不种。然后有个人每天给你一个可以选择一颗植物去促进她生长的机会，问你，至少需要多少天，可以让一定量的植物长的一般高。

思路

看着题我就乐了，数据还小，直接模拟贪心！贪心，启动！

首先啊，为了让这些树的高度差尽可能小，那我们一定是要把化肥给那个矮的，其次啊，我们要去判断谁能先生出种子，然后这个植物基本上就没什么意义了。

如果它到达了可以获得种子的等级，那么我们就贪心的让它获得种子。当我们在选择化肥的时候我们就贪心的选择最容易获得种子的那一个，就可以完美的解决这道题辣。

如果还有哪里不明白，详情请看注释：

Code

#include <bits/stdc++.h>
using namespace std;
int n=1;
int m;
int hp[6];
int higt[100 << 1];
int level[100 << 1];
int ans;
int main()
{
    cin>>hp[0]>>hp[1]>>m;
    hp[2]=1e9;
    for(int i=0;i<m;i++)
    {
        higt[i]=0;
        level[i]=0;
    } // 初始化
    while(n<m)
    {
        ans++;
        int num=n;
        for(int i=0;i<num;i++)
        {
            higt[i]++;
            if(higt[i] >= hp[level[i]]) //如果到达了可以种植的高度
            {
                level[i]++; //把可以获得种子的等级调到下一级
                n++;
            }
        }
        int chemical_fertilizer; //化肥给谁
        if(num == 1)
        {
            chemical_fertilizer =0 ; //就一个，那就给他
        }
        else
        {
            int i,j;
            for(i=1;i<num;i++)
            {
                if(level[i] < 2) // 寻找还没有升到无法获得种子的等级的植物
                {
                    break;
                }
            }
            for(j=i;j<num;j++)
            {
                if(level[j] == 0) //如果是0级，那太棒了就你了
                {
                    break;
                }
            }
            if(j>=num || level[j]!=0) //如果不存在这样的或者上个循环根本没跳出
            {
                chemical_fertilizer = i; //那我选上一个
            }
            else
            {
                chemical_fertilizer=((hp[1]-higt[i])>>1)<((hp[0] - higt[j])>>1)?i:j; //植物争霸赛，看看到底谁到可以种植下一个的时间最短，就给谁施肥
            }
        }
        higt[chemical_fertilizer]++;//获得化肥的再次生长一次！
        if(higt[chemical_fertilizer] >= hp[level[chemical_fertilizer]]) //检查，你要是施了化肥又长出来果子了那就有你好果子吃
        {
            level[chemical_fertilizer]++; //升级
            n++; //植物增多
        }
    }
    for(int i=1;i<m;i++) ans+=higt[0]-higt[i];
    cout<<ans<<endl;
}