弹性伸缩

in Algorithm Pageviews

solve actually problem!

已知由一台或多台机器组成消费者集群，如下所示：

假设消费者集群初始机器台数为1台，集群扩容缩容需要满足下述要求：

  • 扩容是增加机器，没有数量限制；扩容会立即生效，扩容后机器会立刻处理消息；
  • 缩容是减少机器，缩容后集群机器数不能为0；缩容会立即生效，即刻不能继续处理消息。

请实现如下功能：

  1. ScalingSys(int capability) - 初始化系统，集群内每台机器每秒并行消费的信息量为 capability

  2. JudgeWithMsgs(int time, int msgNum) - 系统当且仅当在时刻time进行扩容决策，此时新生产的消息数量为 msgNum (可能为0)

    请按照如下决策此刻集群扩缩容的机器数量，并返回。

    • 决策机制需要平衡成本和平滑性，即扩缩容后，在满足如下条件下使用最少的机器：
    • 假设未来不再扩缩容(即集群的机器数量保持不变)的情况下，截止已收到每批消息都能在其生产后的 5s 内处理完；

    注意：返回时，正数表示扩容，负数表示缩容，值表示数量(0 为既不扩也不缩)

输入

每行表示一个函数调用，初始化函数仅首行调用一次，累计函数调用不超过1000次

1 ≤ capability ≤ 1000, 0 ≤ time ≤ 1000，且 time 严格递增，0 ≤ msgNum ≤ 1000000

输出

答题时按照函数/方法原型中的要求(含返回值)进行实现，输出由框架完成(其首行固定输出null)

样例1

输入样例1：

ScalingSys(10)

JudgeWithMsgs(0, 8)

JudgeWithMsgs(1, 140)

JudgeWithMsgs(2, 41)

JudgeWithMsgs(4, 0)

输出样例1：

null

0

2

1

-1

提示：

  • 时刻0：第一批8条消息到来，可以在5s内完成处理，无需扩容，机器数为1，也无法缩容；
  • 时刻1：第二批140条消息到来，需要在5s内完成处理(即时刻6前)，需要扩容2台机器；
  • 时刻2：第三批剩余110条消息，第三批的41条消息到来，需要再扩容一台机器；
  • 注：时刻3未调用JudgeWithMsgs，不能进行扩缩容决策，只能以现有机器处理消息；
  • 时刻4：第二批剩余的30条消息加上第三批的41条消息，新到来的第四批消息数为0，缩容1台机器，仍然能保证所有消息在生产后5s内完成处理。

样例2

输入样例2：

ScalingSys(2)

JudgeWithMsgs(0, 58)

JudgeWithMsgs(2, 6)

JudgeWithMsgs(5, 0)

JudgeWithMsgs(6, 0)

输出样例2：

null

5

0

-5

0

代码实现如下：

#include <bits/stdc++.h>

using namespace std;

class ScalingSystem {
public:
    ScalingSystem(int capability) : m_cap(capability), m_macNum(1), m_curTime(0)
    {
        std::fill(m_msgNum.begin(), m_msgNum.end(), 0);
    }

    int JudgeWithMsgs(int time, int msgNum)
    {
        int delta = time - m_curTime;
        int totalMsgNum = delta * m_cap * m_macNum;
        for (int i = 0; i < 5; i++) {
            auto consumed = min(totalMsgNum, m_msgNum[i]);
            m_msgNum[i] -= consumed;
            totalMsgNum -= consumed;
        }

        for (int i = 0; i < 5; i++) {
            m_msgNum[i] = (i + delta) < 5 ? m_msgNum[i + delta] : 0;
        }
        
        m_curTime = time;
        m_msgNum[4] = msgNum;
        
        int needMacNum = 0;
        int totalMsg = 0;
        for (int i = 0; i < 5; i++) {
            totalMsg += m_msgNum[i];
            auto divisor = m_cap * (i + 1);
            int curNeed = (totalMsg + divisor - 1) / divisor;
            needMacNum = max(curNeed, needMacNum);
        }
        
        if (needMacNum < 1) {
            needMacNum = 1;
        }

        int res = needMacNum - m_macNum;
        m_macNum = needMacNum;
        return res;
    }

private:
    int m_cap;
    int m_macNum;
    int m_curTime;
    std::array<int, 5> m_msgNum;
};