题目描述

在 $27$ 世纪初，阿尔法·半人马座已成为银河系该区域的主要货运中心。在第四颗行星附近的空间站上，几乎所有太空文明的货物都在此交易并运往各大恒星系。空间站呈大圆环形，外缘有编号为 $1$ 到 $n$（顺时针）的对接港。

当贸易飞船停靠到某个港口时，通常会请求将其货物转运到停靠在其他港口的另一艘飞船。这项任务由在空间站环形轨道内运行的运输机器人（$\text{transrob}$）负责。运输机器人可绕空间站顺时针移动，并在港口装卸货物。

每艘飞船的货物恰好装入一个运输容器，所有运输机器人一次只能携带一个容器。运输机器人仅在其最大载重量上有所不同。

空间站运营联盟近期决定升级运输系统。在此之前，他们希望收集当前系统性能的统计数据。具体来说，他们关注：

1. 请求完成的平均时间，即从飞船请求将货物运往另一港口，到货物实际送达目的地之间的时间。
2. 运输机器人的利用率，即在一段时间内，服务请求的运输机器人的平均百分比。

为此，他们需要一个模拟程序。

输入格式

输入包含多个需要执行的模拟描述。每个描述以一行两个整数 $n$ 和 $m$ 开始，分别表示港口数量和运输机器人数量（$2\le n\le 100$，$1\le m\le 20$）。

接下来 $m$ 行，每行一个整数 $l_i$，表示运输机器人 $i$ 的最大载重量（单位：银河吨）。

然后是一个或多个货运请求。每个请求占一行，包含四个整数 $t$，$o$，$d$，$w$：

• $t$：请求发出时间（从模拟开始计算的分钟数）
• $o$：起点港口号
• $d$：目的地港口号
• $w$：容器重量（银河吨）

输入文件中请求时间严格递增。满足：$1\le t$，$1\le o,d\le n$，$o\ne d$ 和 1≤w≤max⁡{li∣1≤i≤m}1 \leq w \leq \max\{l_i \mid 1 \leq i \leq m\}1≤w≤max{li​∣1≤i≤m}。

货运请求描述以行 -1 -1 -1 -1 结束。

输入以 $n=m=0$ 的测试用例结束，该用例不应处理。

输出格式

对于输入中的每个模拟描述，首先输出描述编号。然后模拟运输机器人在这些货运请求上的操作，输出平均等待时间和利用率百分比。利用率百分比的计算区间为从第一个请求发出到所有请求都被满足的时刻。

模拟开始时（时间 $0$），所有运输机器人空闲，且位于 $1$ 号港口。

所有数值必须精确到小数点后三位。

每个测试用例后输出一个空行。

题目分析与解题思路

关键规则理解

1. 机器人移动规则：运输机器人只能顺时针移动，从一个港口移动到相邻港口需要 $1$ 分钟，装载或卸载货物需要 $5$ 分钟。

2. 机器人分配规则：

   • 所有请求按到达时间顺序处理
   • 当有可满足的请求（存在空闲机器人且货物重量未超过其最大载重）时，立即分配
   • 优先分配较早的请求
   • 每个请求分配给逆时针方向距离请求起点最近的、且能承载该货物重量的运输机器人
   • 如果两个机器人距离相同，则编号较小的获得请求

3. 距离计算的关键理解：

   • 题目要求 closest (in anti-clockwise direction)，即从货物起点逆时针方向最近的机器人
   • 在环形轨道上，从货物 $O$ 逆时针方向到机器人 $R$ 的距离等于从机器人 $R$ 顺时针方向到货物 $O$ 的距离
   • 因此，我们只需要计算从机器人当前位置顺时针到货物起点的距离，然后选择距离最小的机器人即可

4. 时间计算：

   • 机器人服务一个请求的总时间 = 移动到起点时间 + $5$ 分钟装载 + 移动到目的地时间 + $5$ 分钟卸载
   • 请求完成时间 = 从请求发出到货物送达的总时间
   • 机器人忙碌时间 = 从开始服务到完成卸载的时间

算法设计

这是一个典型的离散事件模拟问题。我们需要模拟时间推进过程中请求的到达和机器人的任务执行。

数据结构设计

1. 请求结构体：存储请求的时间、起点、终点、重量等信息
2. 机器人结构体：存储机器人的编号、最大载重、当前位置、可用时间（何时变为空闲）
3. 优先级队列：用于按可用时间排序机器人，便于找到最早可用的机器人

模拟流程

1. 初始化：

   • 所有机器人在港口 $1$，可用时间为 $0$
   • 读取所有请求，按时间顺序存储

2. 主循环：当还有未处理的请求或等待的请求时继续

   • 确定当前时间：取下一个请求到达时间和最早可用机器人的较小值
   • 处理当前时间点：
     • 将所有到达时间不迟于当前时间的请求加入等待队列
     • 将所有可用时间不迟于当前时间的机器人加入空闲队列
   • 尝试分配请求：
     • 按请求到达顺序扫描等待队列
     • 对于每个请求，在空闲机器人中寻找合适的机器人：
       • 机器人载重必须 ≥ 货物重量
       • 选择顺时针距离起点最近的机器人（距离相同时选编号小的）
     • 如果找到合适机器人：
       • 计算服务时间：移动到起点时间 + $10$ 分钟（装载 $5$ + 卸载 $5$）+ 移动到终点时间
       • 更新机器人状态：设置新的可用时间，更新位置
       • 更新统计信息：累加完成时间和忙碌时间
       • 从等待队列中移除该请求
   • 如果没有请求可分配，推进时间到下一个事件点

3. 结果计算：

   • 平均完成时间 = 总完成时间 / 请求数量
   • 利用率 = 总忙碌时间 / （机器人数量 × 时间区间长度）× $100\%$
   • 时间区间长度 = 最后一个请求完成时间 - 第一个请求到达时间

复杂度分析

• 时间复杂度：$O(k\cdot m)$，其中 $k$ 是请求数量，$m$ 是机器人数量。每个请求在最坏情况下需要检查所有机器人。
• 空间复杂度：$O(k+m)$，用于存储请求和机器人的信息。

由于 $n\le 100$，$m\le 20$，$k$ 不会太大（输入保证），这个复杂度是完全可以接受的。

注意事项

1. 精度要求：所有值必须精确到小数点后三位，需要使用 double 类型和 setprecision(3)
2. 边界情况：
   • 没有请求的情况
   • 所有请求同时到达的情况
   • 货物重量超过所有机器人载重的情况（根据输入限制不会发生）
3. 模拟细节：
   • 机器人完成任务后立即变为空闲，可以立即接受新请求
   • 请求分配是瞬时的
   • 需要正确处理环形距离计算

代码实现

// Going in circles on Alpha Centauri
// UVa ID: 660
// Verdict: Accepted
// Submission Date: 2026-01-10
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const int INF = 0x3f3f3f3f;

struct Request {
    int time, origin, dest, weight;
};

struct Robot {
    int id, maxLoad, location, available;
    // 优先队列，完成时间早的机器人排在前
    bool operator < (const Robot r) const { return available > r.available; }
};

int n, m;

int clockwiseTime(int from, int to) {
    return to >= from ? to - from : n - (from - to);
}

pair<double, double> simulate() {
    vector<Robot> idling;
    priority_queue<Robot> working;
    for (int i = 0; i < m; ++i) {
        int load; cin >> load;
        working.push({i + 1, load, 1, 0});
    }
    vector<Request> appending, waiting;
    while (true) {
        int t, o, d, w; cin >> t >> o >> d >> w;
        if (t == -1) break;
        appending.push_back({t, o, d, w});
    }
    if (appending.empty()) return {0.0, 0.0};

    int cntOfRequest = appending.size();
    int startTime = appending.front().time;
    int currentTime = 0, waitTime = 0, serviceTime = 0;

    while (!waiting.empty() || !appending.empty()) {
        // 更新当前时间，取到达的请求和最早完成任务的机器人的较小值
        currentTime = INF;
        if (appending.size()) currentTime = appending.front().time;
        if (working.size()) currentTime = min(currentTime, working.top().available);
        // 将到达时间不迟于当前时间的请求放入等待队列
        while (!appending.empty() && appending.front().time <= currentTime) {
            waiting.push_back(appending.front());
            appending.erase(appending.begin());
        }
        // 将可用时间不迟于当前时间的机器人放入可用机器人队列
        while (!working.empty() && working.top().available <= currentTime) {
            idling.push_back(working.top());
            working.pop();
        }
        // 扫描当前等待请求队列，安排机器人服务
        vector<int> assigned;
        for (int i = 0; i < waiting.size(); i++) {
            int bestIdx = -1, bestId = INF, bestDist = INF;
            for (int j = 0; j < idling.size(); j++) {
                if (idling[j].maxLoad < waiting[i].weight) continue;
                int d = clockwiseTime(idling[j].location, waiting[i].origin);
                if (d < bestDist || (d == bestDist && idling[j].id < bestId)) {
                    bestDist = d;
                    bestId = idling[j].id;
                    bestIdx = j;
                }
            }
            // 找到可用机器人
            if (bestIdx >= 0) {
                // 计算服务时间
                int d1 = clockwiseTime(idling[bestIdx].location, waiting[i].origin);
                int d2 = clockwiseTime(waiting[i].origin, waiting[i].dest);
                serviceTime += d1 + 10 + d2;
                waitTime += currentTime - waiting[i].time + d1 + 10 + d2;
                // 将当前机器人放入工作机器人优先队列
                Robot robot = idling[bestIdx];
                robot.location = waiting[i].dest;
                robot.available = currentTime + d1 + 10 + d2;
                working.push(robot);
                // 从可用机器人队列移除
                idling.erase(idling.begin() + bestIdx);
                // 标记任务已服务
                assigned.push_back(i);
             }
        }
        // 将已经服务的请求从等待队列中移除
        for (auto it = assigned.rbegin(); it != assigned.rend(); it++)
            waiting.erase(waiting.begin() + *it);
    }
    // 更新服务结束时间
    while (!working.empty()) {
        currentTime = working.top().available;
        working.pop();
    }
    double averageTime = (double)waitTime / cntOfRequest;
    double utilization = (double)serviceTime / (m * (currentTime - startTime)) * 100.0;
    return {averageTime, utilization};
}

int main() {
    int T = 0;
    while (cin >> n >> m, n) {
        T++;
        auto result = simulate();
        cout << "Simulation " << T << '\n';
        cout << fixed << setprecision(3);
        cout << "Average wait time   = " << result.first << " minutes\n";
        cout << "Average utilization = " << result.second << " %\n\n";
    }
    return 0;
}

总结

本题是一个典型的模拟问题，主要考察对题目规则的理解和实现细节的把握。关键点在于：

1. 正确理解距离计算：认识到"货物逆时针方向最近的机器人"等价于"机器人顺时针到货物起点距离最小的机器人"
2. 设计合适的模拟流程：使用事件驱动的方式，正确处理时间推进和状态更新
3. 注意统计计算：准确计算完成时间和利用率，满足精度要求

通过本题，我们可以学习到如何将实际问题转化为可计算的模拟模型，以及如何处理环形结构上的距离计算和时间调度问题。