云服务资源调度

题意

有 个任务，每个任务有一个计算成本 。服务器的最大计算容量为 。为每台服务器分配任务时，采用贪心策略：总是优先选择当前未分配的、计算成本最高的、且不超出剩余容量的任务。问处理完所有任务最少需要多少台服务器。

思路

题目描述的其实是一个确定性的装箱模拟：每开一台新服务器，就从剩余任务中反复挑最大的能放进去的，直到再也放不进，然后开下一台。

具体流程：

  1. 把任务按成本从大到小排序。
  2. 遍历任务，遇到第一个还没被分配的任务，就开一台新服务器，把这个任务放进去。
  3. 接着从剩余任务中扫描，每次挑最大的且不超出剩余容量的任务放进去，直到没有能放的为止。
  4. 重复 2-3 直到所有任务都被分配。

有一个容易踩的坑：任务的计算成本可能超过服务器容量 。这种任务无法和别的任务拼在一起，但仍然需要占一台服务器。如果在代码里先设 remaining = c 再扫描，超过 的任务永远不满足 cost <= remaining，就会被漏掉。正确的做法是：开服务器时先把这个任务"强制放入"（used[i] = true, remaining = c - cost[i]），这样即使 remaining 变成负数，该任务也不会被遗漏。

为什么排序后从大到小开服务器、然后向小端扫描是对的？

因为大任务"挤占"容量多，越早安排越好。大任务开了一台服务器之后，剩余空间只能塞比它小的任务。从大到小扫描，遇到第一个能放进去的就是"最大的能放进去的"，符合题目的贪心规则。

拿样例验证一下：容量 ，排序后 。

服务器 放入任务 使用容量
1 98, 9 107
2 98, 8 106
3 78, 32 110
4 73, 31 104
5 54, 51 105
6 46, 44 90
7 27 27

一共 7 台，和答案一致。

复杂度

  • 时间：，排序 ，模拟最坏情况每台服务器扫描一遍数组
  • 空间：

代码

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<long long> costs(n);
    for (int i = 0; i < n; i++) cin >> costs[i];
    long long c;
    cin >> c;

    sort(costs.begin(), costs.end());
    vector<bool> used(n, false);
    int servers = 0;

    for (int i = n - 1; i >= 0; i--) {
        if (used[i]) continue;
        servers++;
        used[i] = true;
        long long remaining = c - costs[i];

        for (int j = i - 1; j >= 0; j--) {
            if (!used[j] && costs[j] <= remaining) {
                used[j] = true;
                remaining -= costs[j];
                if (remaining == 0) break;
            }
        }
    }

    cout << servers << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);

        st.nextToken(); int n = (int) st.nval;
        long[] costs = new long[n];
        for (int i = 0; i < n; i++) {
            st.nextToken();
            costs[i] = (long) st.nval;
        }
        st.nextToken(); long c = (long) st.nval;

        Arrays.sort(costs);
        boolean[] used = new boolean[n];
        int servers = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (used[i]) continue;
            servers++;
            used[i] = true;
            long remaining = c - costs[i];

            for (int j = i - 1; j >= 0; j--) {
                if (!used[j] && costs[j] <= remaining) {
                    used[j] = true;
                    remaining -= costs[j];
                    if (remaining == 0) break;
                }
            }
        }

        System.out.println(servers);
    }
}

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    costs = []
    for i in range(n):
        costs.append(int(input_data[idx])); idx += 1
    c = int(input_data[idx]); idx += 1

    costs.sort()
    used = [False] * n
    servers = 0

    for i in range(n - 1, -1, -1):
        if used[i]:
            continue
        servers += 1
        used[i] = True
        remaining = c - costs[i]

        for j in range(i - 1, -1, -1):
            if not used[j] and costs[j] <= remaining:
                used[j] = True
                remaining -= costs[j]
                if remaining == 0:
                    break

    print(servers)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];

rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const costs = lines[1].split(/\s+/).map(Number);
    const c = parseInt(lines[2]);

    costs.sort((a, b) => a - b);
    const used = new Array(n).fill(false);
    let servers = 0;

    for (let i = n - 1; i >= 0; i--) {
        if (used[i]) continue;
        servers++;
        used[i] = true;
        let remaining = c - costs[i];

        for (let j = i - 1; j >= 0; j--) {
            if (!used[j] && costs[j] <= remaining) {
                used[j] = true;
                remaining -= costs[j];
                if (remaining === 0) break;
            }
        }
    }

    console.log(servers);
});