题解 | #云服务资源调度#

题目链接

云服务资源调度

题目描述

一个云计算平台需要调度一批任务，每个任务有其计算成本 $c_i$ 。平台拥有一批服务器，每台服务器的最大计算容量为 $m$ 。

任务分配遵循一种贪心策略：为一台服务器分配任务时，总是优先选择 当前未分配的、计算成本最高的、且不会超出服务器剩余容量的 任务。当一台服务器无法再装入任何未分配的任务时，再启用一台新服务器，并重复此过程。

你需要计算，处理完所有任务最少需要多少台服务器。

输入:

第一行一个整数 $n$ ，表示任务总数。
第二行 $n$ 个整数，表示每个任务的计算成本 $c_i$ 。
第三行一个整数 $m$ ，表示每台服务器的最大计算容量。

输出:

一个整数，代表处理所有任务所需的最少服务器数量。

解题思路

我们必须严格遵循题目描述的贪心策略：为一台新服务器分配任务时，循环地从中挑选 当前未分配的、成本最高的、且能装下的 任务。一个高效且正确的实现流程如下：

数据结构选择
- 我们需要一个能动态管理所有未分配任务，并支持高效查找最大/次大元素和删除操作的有序数据结构。
- C++: std::multiset 是理想选择。
- Java: TreeMap<Integer, Integer> 用来存储 (任务成本 -> 数量) 的映射。
- Python: collections.Counter 结合一个有序的键列表来实现。
算法流程
- 将所有任务成本存入所选的数据结构中。
- 初始化服务器数量 server_count = 0。
- 进入一个主循环，只要还有任务未被分配就继续： a. server_count 加 1，代表启用一台新服务器。 b. 优先分配最大任务：首先，从数据结构中找到并移除当前全局成本最高的任务。将其分配给新服务器，并更新服务器的剩余容量 current_capacity。 c. 填充剩余容量：接着，进入一个内部循环，用 current_capacity 继续填充： i. 在数据结构中，查找不大于 current_capacity 的最大任务。 ii. 如果找到了这样的任务，就将其分配，更新 current_capacity 并从数据结构中移除。 iii. 如果找不到，说明服务器已无法装入更多任务，跳出内部循环。
- 主循环结束后，server_count 即为最终答案。

这种“先取最大，再填充剩余”的策略完全符合题意，并能有效规避性能陷阱。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    multiset<int> costs;
    for (int i = 0; i < n; ++i) {
        int cost;
        cin >> cost;
        costs.insert(cost);
    }

    int m;
    cin >> m;

    int server_count = 0;
    while (!costs.empty()) {
        server_count++;
        
        // 优先处理当前未分配的、成本最高的任务
        auto it_largest = prev(costs.end());
        int current_capacity = m - *it_largest;
        costs.erase(it_largest);

        // 继续为这台服务器填充其他能装下的、成本最高的任务
        while (current_capacity > 0 && !costs.empty()) {
            // 查找不大于 current_capacity 的最大元素
            auto it_to_take = costs.upper_bound(current_capacity);

            // 如果没有元素小于或等于 current_capacity，则跳出
            if (it_to_take == costs.begin()) {
                break;
            }
            
            // 退一位，指向目标元素
            it_to_take--;

            current_capacity -= *it_to_take;
            costs.erase(it_to_take);
        }
    }

    cout << server_count << endl;

    return 0;
}

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        TreeMap<Integer, Integer> costs = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int cost = sc.nextInt();
            costs.put(cost, costs.getOrDefault(cost, 0) + 1);
        }

        int m = sc.nextInt();

        int serverCount = 0;
        int assignedTasks = 0;
        
        while (assignedTasks < n) {
            serverCount++;
            
            // 1. 优先处理全局最大的任务
            int largestTask = costs.lastKey();
            int currentCapacity = m - largestTask;
            assignedTasks++;
            
            int count = costs.get(largestTask);
            if (count == 1) {
                costs.remove(largestTask);
            } else {
                costs.put(largestTask, count - 1);
            }

            // 2. 填充剩余容量
            while (currentCapacity > 0 && assignedTasks < n) {
                Integer taskToTake = costs.floorKey(currentCapacity);

                if (taskToTake == null) {
                    break; // 没有能装下的任务了
                }

                currentCapacity -= taskToTake;
                assignedTasks++;

                int innerCount = costs.get(taskToTake);
                if (innerCount == 1) {
                    costs.remove(taskToTake);
                } else {
                    costs.put(taskToTake, innerCount - 1);
                }
            }
        }
        System.out.println(serverCount);
    }
}

import collections
import bisect

def main():
    n = int(input())
    cost_list = list(map(int, input().split()))
    m = int(input())

    if n == 0:
        print(0)
        return

    counts = collections.Counter(cost_list)
    sorted_keys = sorted(counts.keys())
    
    server_count = 0
    assigned_tasks = 0

    while assigned_tasks < n:
        server_count += 1
        
        # 1. 优先处理全局最大的任务
        largest_task = sorted_keys[-1]
        current_capacity = m - largest_task
        
        counts[largest_task] -= 1
        if counts[largest_task] == 0:
            sorted_keys.pop()
        assigned_tasks += 1

        # 2. 填充剩余容量
        while current_capacity > 0 and assigned_tasks < n:
            # 查找不大于 current_capacity 的最大成本的位置
            idx = bisect.bisect_right(sorted_keys, current_capacity)
            
            if idx == 0:
                # 没有任何任务能装下
                break

            # 从该位置向前找一个数量不为0的任务
            best_key_idx = -1
            for i in range(idx - 1, -1, -1):
                if counts[sorted_keys[i]] > 0:
                    best_key_idx = i
                    break
            
            if best_key_idx != -1:
                task_cost = sorted_keys[best_key_idx]
                current_capacity -= task_cost
                counts[task_cost] -= 1
                assigned_tasks += 1
                if counts[task_cost] == 0 and best_key_idx == len(sorted_keys) - 1:
                    # 只在用完的是当前最大成本任务时才pop，避免O(N)的删除
                    sorted_keys.pop()
            else:
                # 在可装载的成本范围内，没有可用的任务了
                break

    print(server_count)

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心、模拟、有序集合/映射
时间复杂度： $\mathcal{O}(N \log N)$ 。初始化数据结构需要 $\mathcal{O}(N \log N)$ 。在模拟过程中，每个任务只会被查找和删除一次，每次操作的复杂度是 $\mathcal{O}(\log K)$ （其中 $K$ 是当前不同任务成本的数量， $K \le N$ ）。因此，总的模拟过程复杂度也是 $\mathcal{O}(N \log N)$ 。
空间复杂度： $\mathcal{O}(N)$ ，用于存储所有任务成本的数据结构。