REALHW84 星港交通调度

题目链接

星港交通调度

题目描述

在“天穹站”太空港，你需要为 艘申请停泊的星舰分配泊位。空间站共分 个层级，每层有 个泊位。

停泊规则:

  • 每艘星舰 有一个首选停泊层级 和船员人数 。
  • 星舰只能被安排在其首选层级或其下方的任意层级（直至最底部的1层）。

能源消耗:

  • 总能耗公式: 对于一艘首选层级为 ，最终停在 层 ()，载有 名船员的星舰，其单次任务能耗为: 。

任务目标: 为所有 艘星舰找到一个停泊方案，使得总能耗（所有星舰的能耗之和）达到最小值。如果泊位不足以容纳所有星舰，则输出 -1。

解题思路

这是一道贪心算法优化问题。我们的目标是最小化所有星舰的总能耗。

首先，分析总能耗公式:

展开这个和式:

在这个表达式中，第一部分 是一个常数。因此，要使 最小，我们必须最大化第二部分 。

问题转化为：如何为星舰分配停泊层级 ，以最大化所有星舰的“船员数 停泊层级”之和。为了实现这一目标，我们应该遵循一个贪心原则：将船员数量更多 ( 值大) 的星舰，安排在尽可能高 ( 值大) 的可用层级。

基于此，我们设计出如下的贪心算法：

  1. 数据预处理: 将所有星舰按照其首选层级 分组。同时，计算出能耗公式中的常量部分 。
  2. 贪心分配:
    • 我们从最高层级 开始，向下遍历至层级 1。
    • 维护一个“候选池”（大顶堆），存放所有当前可以停泊但尚未分配泊位的星舰。
    • 当遍历到层级 时，将所有首选层级为 的星舰全部加入大顶堆中。
    • 从大顶堆中连续取出船员数最多的星舰，最多取 次，并将它们安排在当前层级 。
  3. 最终检查: 在贪心分配结束后，必须检查是否所有 艘星舰都被成功分配。即使总泊位 F*M 大于等于 N，也可能因为局部泊位不足（例如所有星舰都申请停在高层）导致无法安排。如果成功分配的星舰总数小于 ，则说明方案不可行，应输出 -1。
  4. 计算最终结果: 如果所有星舰都成功分配，则计算最终能耗。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

    long long f, m, n;
    cin >> f >> m >> n;

    if (n > f * m) {
        cout << -1 << endl;
        return 0;
    }

    vector<vector<int>> ships_by_pref(f + 1);
    long long total_cost = 0;

    for (int i = 0; i < n; ++i) {
        int r, p;
        cin >> r >> p;
        ships_by_pref[r].push_back(p);
        // 先累加能耗公式中的固定部分 P * (2 + R)
        total_cost += (long long)p * (2 + r);
    }

    priority_queue<int> available_ships; 
    long long assigned_ships_count = 0;

    for (int current_level = f; current_level >= 1; --current_level) {
        for (int crew : ships_by_pref[current_level]) {
            available_ships.push(crew);
        }

        for (int i = 0; i < m && !available_ships.empty(); ++i) {
            int top_crew = available_ships.top();
            available_ships.pop();
            
            // 减去通过贪心最大化的 P * A 部分
            total_cost -= (long long)top_crew * current_level;
            assigned_ships_count++;
        }
    }

    if (assigned_ships_count < n) {
        cout << -1 << endl;
    } else {
        cout << total_cost << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long f = sc.nextLong();
        long m = sc.nextLong();
        long n = sc.nextLong();

        if (n > f * m) {
            System.out.println(-1);
            return;
        }

        List<List<Integer>> shipsByPref = new ArrayList<>();
        for (int i = 0; i <= f; i++) {
            shipsByPref.add(new ArrayList<>());
        }

        long totalCost = 0;
        for (int i = 0; i < n; i++) {
            int r = sc.nextInt();
            int p = sc.nextInt();
            shipsByPref.get(r).add(p);
            // 先累加能耗公式中的固定部分 P * (2 + R)
            totalCost += (long)p * (2 + r);
        }

        PriorityQueue<Integer> availableShips = new PriorityQueue<>(Collections.reverseOrder());
        long assignedShipsCount = 0;
        
        for (int currentLevel = (int)f; currentLevel >= 1; currentLevel--) {
            for (int crew : shipsByPref.get(currentLevel)) {
                availableShips.add(crew);
            }

            for (int i = 0; i < m && !availableShips.isEmpty(); i++) {
                int topCrew = availableShips.poll();
                // 减去通过贪心最大化的 P * A 部分
                totalCost -= (long)topCrew * currentLevel;
                assignedShipsCount++;
            }
        }
        
        if (assignedShipsCount < n) {
            System.out.println(-1);
        } else {
            System.out.println(totalCost);
        }
    }
}

import heapq

def solve():
    f, m, n = map(int, input().split())

    if n > f * m:
        print(-1)
        return

    ships_by_pref = [[] for _ in range(f + 1)]
    total_cost = 0

    for _ in range(n):
        r, p = map(int, input().split())
        ships_by_pref[r].append(p)
        # 先累加能耗公式中的固定部分 P * (2 + R)
        total_cost += p * (2 + r)

    available_ships_heap = []
    assigned_ships_count = 0
    
    for current_level in range(f, 0, -1):
        for crew in ships_by_pref[current_level]:
            heapq.heappush(available_ships_heap, -crew)

        for _ in range(m):
            if not available_ships_heap:
                break
            
            top_crew_neg = heapq.heappop(available_ships_heap)
            crew = -top_crew_neg
            
            # 减去通过贪心最大化的 P * A 部分
            total_cost -= crew * current_level
            assigned_ships_count += 1

    if assigned_ships_count < n:
        print(-1)
    else:
        print(total_cost)

solve()

算法及复杂度

  • 算法: 贪心算法, 优先队列 (堆)
  • 时间复杂度:
  • 空间复杂度: