题解 | #牛牛的导弹系统#

思路：

题目的主要信息：

• 求最少需要布置x个导弹系统
• 其中每个导弹系统每天只能发射一枚导弹，但是我们一天总计要发射至少M枚
• 导弹系统一经发射，必须连续发射A天，且需要休息B天不能发射
• 导弹系统在交接的时候，至少需要有一个导弹系统是可以工作的

方法一：暴力模拟法
具体做法：
首先如果，我们只需要安排M个导弹系统在前A天发射，M个导弹系统在后B天发射，但是因为要在交接时前面的还没休息好，如果至少需要有一个导弹系统可以发射，因此我们还要多备M个，因此这种情况是个系统；
再来，这种情况下导弹需要交接的时候前面已经休息好了，可以直接使用，因此我们可以不用多备，结果是个系统；
最后如果，我们可以直接暴力模拟一个循环，这种情况下需要多少：使用辅助数组temp表示每天空闲的导弹系统，利用贪心思想，如果temp[i]不足M或者第二天的没有剩余可以用，就增加导弹系统，同时后面A天都有这个导弹系统，需要同步增加。

class Solution {
public:
    int solve(int A, int B, int M) {
        if(A == B)
            return 3 * M; //交接时候需要
        if(A > B)
            return 2 * M; //不需要交接天数
        vector<short> temp(A + B + 1, 0);  //辅助数组，int型段错误
        int res = 0;
        temp[A + B] = 1;
        for(int i = 0; i < A + B; i++){ //循环一周
            while(temp[i] < M || (temp[i] >= M && temp[i + 1] == 0)){ //当天不足或者第二天的没有备用
                res++;
                for(int j = i; j < i + A; j++) //后面几天都有了
                    temp[j]++;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况，上述代码中三层循环全部遍历
• 空间复杂度：，辅助数组temp的长度

方法二：数学+分类讨论
具体做法：
前面两种情况见方法一。
当时，由于休息时间长于连续发射时间，我们一共需要个系统才能保证每天至少发射颗，然后还需要加上交接的M个系统，因此一个循环后前面休息的肯定没准备好。

class Solution {
public:
    int solve(int A, int B, int M) {
        if(A == B)
            return 3 * M; //交接时候需要
        if(A > B)
            return 2 * M; //不需要交接天数
        else
            return M * ((B / A) + 2); //其余情况
    }
};

复杂度分析：

• 时间复杂度：，直接判断给出答案
• 空间复杂度：，无额外空间使用