星港交通调度

题目描述

空间站有 个停泊层级，每层有 个标准化泊位。 艘星舰申请停泊，每艘星舰 有首选层级 和船员数 。星舰只能停在首选层级或其下方任意层级。

停泊能耗公式：对于首选层级 、最终停在第 层、载有 名船员的星舰，能耗为 。

求所有星舰总能耗的最小值，若泊位不足输出 。

思路分析

关键转化

将总能耗展开：

$$

第一项 是常量（与分配方案无关）。因此，最小化总能耗等价于最大化 。

贪心策略

要最大化 ，直觉上应让船员数大的星舰尽量停在高层级。

从最高层级 向下遍历到第 层：

1. 将首选层级等于当前层级的星舰加入候选池。
2. 若候选池中星舰数 ，全部停在当前层级。
3. 若候选池中星舰数 ，按船员数降序排序，前 艘停在当前层级，其余溢出到下一层级继续参与分配。

为什么这样是最优的？ 高层级对 的贡献更大，而船员数 是该贡献的系数。在每一层，将船员数最大的 艘留下，能使它们乘以尽可能大的层级编号，从而最大化总贡献。溢出的低船员数星舰即使下移，损失也最小。

不可行判断

处理完第 层后，若候选池中仍有星舰未被分配（无法再下移），则输出 。

代码

[sol-C++]

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

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);

    vector<vector<int>> ships(n + 1);
    long long constantPart = 0;
    for(int i = 0; i < k; i++){
        int p, c;
        scanf("%d%d", &p, &c);
        ships[p].push_back(c);
        constantPart += (long long)c * (2 + p);
    }

    long long sumCQ = 0;
    vector<int> overflow;

    for(int level = n; level >= 1; level--){
        for(int c : ships[level]){
            overflow.push_back(c);
        }

        if((int)overflow.size() <= m){
            for(int c : overflow){
                sumCQ += (long long)c * level;
            }
            overflow.clear();
            continue;
        }

        sort(overflow.begin(), overflow.end(), greater<int>());

        for(int i = 0; i < m; i++){
            sumCQ += (long long)overflow[i] * level;
        }

        overflow = vector<int>(overflow.begin() + m, overflow.end());
    }

    if(!overflow.empty()){
        printf("-1\n");
    } else {
        printf("%lld\n", constantPart - sumCQ);
    }
    return 0;
}

[sol-Java]

import java.util.*;

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

        List<List<Integer>> ships = new ArrayList<>();
        for (int i = 0; i <= n; i++) ships.add(new ArrayList<>());

        long constantPart = 0;
        for (int i = 0; i < k; i++) {
            int p = sc.nextInt(), c = sc.nextInt();
            ships.get(p).add(c);
            constantPart += (long) c * (2 + p);
        }

        long sumCQ = 0;
        List<Integer> overflow = new ArrayList<>();

        for (int level = n; level >= 1; level--) {
            overflow.addAll(ships.get(level));

            if (overflow.size() <= m) {
                for (int c : overflow) {
                    sumCQ += (long) c * level;
                }
                overflow.clear();
                continue;
            }

            overflow.sort(Collections.reverseOrder());

            for (int i = 0; i < m; i++) {
                sumCQ += (long) overflow.get(i) * level;
            }

            overflow = new ArrayList<>(overflow.subList(m, overflow.size()));
        }

        if (!overflow.isEmpty()) {
            System.out.println(-1);
        } else {
            System.out.println(constantPart - sumCQ);
        }
    }
}

[sol-Python3]

import sys
input = sys.stdin.readline

def main():
    n, m, k = map(int, input().split())
    ships = [[] for _ in range(n + 1)]
    constant_part = 0
    for _ in range(k):
        p, c = map(int, input().split())
        ships[p].append(c)
        constant_part += c * (2 + p)

    sum_cq = 0
    overflow = []

    for level in range(n, 0, -1):
        overflow.extend(ships[level])

        if len(overflow) <= m:
            for c in overflow:
                sum_cq += c * level
            overflow.clear()
            continue

        overflow.sort(reverse=True)

        for i in range(m):
            sum_cq += overflow[i] * level

        overflow = overflow[m:]

    if overflow:
        print(-1)
    else:
        print(constant_part - sum_cq)

main()

[sol-JavaScript]

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, m, k] = lines[0].split(' ').map(Number);
    const ships = Array.from({length: n + 1}, () => []);
    let constantPart = 0;

    for (let i = 1; i <= k; i++) {
        const [p, c] = lines[i].split(' ').map(Number);
        ships[p].push(c);
        constantPart += c * (2 + p);
    }

    let sumCQ = 0;
    let overflow = [];

    for (let level = n; level >= 1; level--) {
        overflow.push(...ships[level]);

        if (overflow.length <= m) {
            for (const c of overflow) {
                sumCQ += c * level;
            }
            overflow = [];
            continue;
        }

        overflow.sort((a, b) => b - a);

        for (let i = 0; i < m; i++) {
            sumCQ += overflow[i] * level;
        }

        overflow = overflow.slice(m);
    }

    if (overflow.length > 0) {
        console.log(-1);
    } else {
        console.log(constantPart - sumCQ);
    }
});

复杂度分析

• 时间复杂度：，最坏情况下每层都需要对候选池排序。由于 ，完全可以接受。
• 空间复杂度：，存储各层星舰和溢出队列。