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

题意分析

• 需要在每一天至少发射M枚炮弹。
• 在进行交接的时候必须至少有一个系统可以正常发射。
• 每个系统发射的时间为A天，冷却的时间为B天。
• 问至少需要部署多少个导弹系统可以保证符合上述要求。

  思路分析

• 首先，我们发现可以把A+B看作是一个周期，因为这个周期过后之前冷却的有可以继续使用了，相当于进入了下一个新的周期。
• 然后，我们对A和B的情况进行分类
  • A<B
    
  • A=B
    
  • A>B
    

写法一

• 经过上面的分析，我们的问题就迎刃而解了。

• 代码如下

  • 直接得到答案，时间复杂度为O(1)
  • 没有开多余的空间，空间复杂度为O(1)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型 可以连续发射A天
     * @param B int整型 需要连续冷却B天
     * @param M int整型 每天至少需要发射M粒导弹
     * @return int整型
     */
    int solve(int A, int B, int M) {
        // write code here
        if(A==B){
            return 3*M;
        }else if(A>B){
            return M*2;
        }else{
            int tmp=(B/A);
            return M+(tmp+1)*M;
        }
    }
};

写法二

• 我们继续对第一种写法进行分析。我们发现，其实分析A<B的情况的时候我们就可以得到所有的情况。根据A<B的分析方法具有普遍性。所以我们可以一个公式表示最后的结果

• 代码如下

  • 直接计算公式，时间复杂度为
  • 基本没有开多余空间，空间复杂度为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型 可以连续发射A天
     * @param B int整型 需要连续冷却B天
     * @param M int整型 每天至少需要发射M粒导弹
     * @return int整型
     */
    int solve(int A, int B, int M) {
        // write code here
        return (B/A+2)*M;
    }
};