部署虚拟机

02 Sep 2024 in Algorithm Pageviews

solve actually problem!

虚拟化技术，可以在一台物理机上部署一个或多个虚拟机，以优化资源的使用，常用的VMware可以做到在一台物理机上部署多个虚拟机。

现在有一批物理机记录在数组 capa 中，capa[i]表示编号为 i 的物理机初始内存大小；同时给出一批虚拟机部署请求方案 requests ，其元素依次表示待部署的请求中所需要的虚拟机的内存大小。

请按如下规则依次处理 requests 中的每个虚拟机部署请求，并返回每个虚拟机部署所在的物理机编号(或者-1)：

• 如果没有物理机的可用内存大于等于待部署的虚拟机所需内存，则该虚拟机部署失败，返回-1。
• 否则，按照以下方式选择一台物理机用于部署这个虚拟机，返回选中物理机的编号：
  • 优先选择可用内存最大的物理机。
  • 如果可用内存最大的物理机有多台，则在其中选择当前已部署虚拟机数量最少的物理机。
  • 如果当前已部署虚拟机数量最少的物理机仍有多台，则在其中选择编号最小的物理机。

样例

输入：

[10, 32, 32, 64]

[32, 16, 33]

输出：

[3, 1, -1]

解释：

第一个虚拟机需要的内存大小为32，在可用内存最大的物理机3上部署(部署后剩余内存为32)。

第二个虚拟机需要内存为16，此时物理机1，2，3的可用内存大小均为32，但是物理机3已经部署了一个虚拟机，因此优先在物理机1，2上部署。由于物理机1，2上都未部署，因此选择编号最小的物理机1。

第三个虚拟机需要内存大于33的物理机，所以会部署失败。

代码实现如下:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> DispatchRequests(const vector<int> &caps, const vector<int> &requests)
    {
        auto Com = [](tuple<int, int, int> &a, tuple<int, int, int> &b) {
            return (make_tuple(get<0>(a), -get<1>(a), -get<2>(a)) <
                    make_tuple(get<0>(b), -get<1>(b), -get<2>(b)));
        };

        using TUP = tuple<int, int, int>; // 剩余内存，部署数量，物理机序号
        priority_queue<TUP, vector<TUP>, decltype(Com)> pq(Com);
        for (int i = 0; i < caps.size(); i++) {
            pq.push({caps[i], 0, i});
        }

        vector<int> ans;
        for (auto &item : requests) {
            auto [cap, num, idx] = pq.top();
            pq.pop();
            if (cap >= item) {
                cap -= item;
                num++;
                ans.push_back(idx);
            } else {
                ans.push_back(-1);
            }
            
            pq.push({cap, num, idx});
        }
        return ans;
    }
};