题意分析

本题模拟了一个环形港口（n个港口）中多个运输机器人（m个）处理运输请求的场景。每个请求包含：请求时间、起始港口、目标港口和货物重量。运输机器人有不同载重能力，需要选择最合适的机器人来处理请求，目标是计算平均等待时间和机器人利用率。

解题思路

1. 输入处理：

   • 读取港口数量n和机器人数量m。
   • 读取每个机器人的最大载重capacities。
   • 读取运输请求，直到遇到终止标记(-1, -1, -1, -1)。

2. 机器人选择策略：

   • 对于每个请求，遍历所有机器人，选择满足以下条件的机器人：
     • 载重足够（maxLoad >= weight）。
     • 当前空闲（busyUntil <= request.time）。
     • 距离起始港口最近的机器人（若距离相同，选择编号小的）。

3. 时间计算：

   • 到达时间：机器人从当前位置移动到起始港口的时间。
   • 装载时间：固定5分钟。
   • 运输时间：从起始港口到目标港口的距离。
   • 卸载时间：固定5分钟。
   • 总处理时间：到达时间 + 装载时间 + 运输时间 + 卸载时间。

4. 统计指标：

   • 平均等待时间：所有请求从提交到完成的平均时间。
   • 利用率：机器人忙碌时间占总时间的百分比。

5. 输出结果：

   • 按格式输出平均等待时间和利用率，保留3位小数。

完整代码

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
#include <algorithm>

using namespace std;

struct Request {
    int time;
    int origin;
    int destination;
    int weight;
    int startTime;
    int endTime;
};

struct Transrob {
    int id;
    int maxLoad;
    int currentPort;
    int busyUntil;
};

bool compareRequests(const Request& a, const Request& b) {
    return a.time < b.time;
}

int calculateDistance(int n, int from, int to) {
    if (to >= from) return to - from;
    return n - (from - to);
}

void simulate(int n, int m, vector<int>& capacities, vector<Request>& requests) {
    vector<Transrob> transrobs(m);
    for (int i = 0; i < m; ++i) {
        transrobs[i].id = i + 1;
        transrobs[i].maxLoad = capacities[i];
        transrobs[i].currentPort = 1;
        transrobs[i].busyUntil = 0;
    }

    int totalWaitTime = 0;
    int totalBusyTime = 0;
    int firstRequestTime = requests.empty() ? 0 : requests[0].time;
    int lastCompletionTime = 0;

    for (size_t i = 0; i < requests.size(); ++i) {
        Request& req = requests[i];
        int bestTransrob = -1;
        int minDistance = n + 1;

        for (int j = 0; j < m; ++j) {
            if (transrobs[j].maxLoad >= req.weight && 
                transrobs[j].busyUntil <= req.time) {
                int distance = calculateDistance(n, transrobs[j].currentPort, req.origin);
                if (distance < minDistance || 
                    (distance == minDistance && transrobs[j].id < transrobs[bestTransrob].id)) {
                    bestTransrob = j;
                    minDistance = distance;
                }
            }
        }

        if (bestTransrob != -1) {
            Transrob& t = transrobs[bestTransrob];
            int arrivalTime = req.time + minDistance;
            int loadTime = arrivalTime + 5;
            int travelTime = calculateDistance(n, req.origin, req.destination);
            int unloadTime = loadTime + travelTime + 5;
            
            req.startTime = arrivalTime;
            req.endTime = unloadTime;
            totalWaitTime += (unloadTime - req.time);
            
            t.busyUntil = unloadTime;
            t.currentPort = req.destination;
            totalBusyTime += (unloadTime - max(req.time, t.busyUntil - (unloadTime - req.time)));
            
            if (unloadTime > lastCompletionTime) {
                lastCompletionTime = unloadTime;
            }
        }
    }

    double avgWaitTime = requests.empty() ? 0 : (double)totalWaitTime / requests.size();
    double utilization = (firstRequestTime == lastCompletionTime) ? 0 : 
                        (double)totalBusyTime / (m * (lastCompletionTime - firstRequestTime)) * 100;

    cout << fixed << setprecision(3);
    cout << "Average wait time   = " << avgWaitTime << " minutes" << endl;
    cout << "Average utilization = " << utilization << " %" << endl;
}

int main() {
    int n, m;
    int caseNum = 0;
    
    while (cin >> n >> m && (n != 0 || m != 0)) {
        caseNum++;
        vector<int> capacities(m);
        for (int i = 0; i < m; ++i) {
            cin >> capacities[i];
        }
        
        vector<Request> requests;
        while (true) {
            int t, o, d, w;
            cin >> t >> o >> d >> w;
            if (t == -1 && o == -1 && d == -1 && w == -1) break;
            Request req = {t, o, d, w, 0, 0};
            requests.push_back(req);
        }
        
        cout << "Simulation " << caseNum << endl;
        simulate(n, m, capacities, requests);
        cout << endl;
    }
    
    return 0;
}