#P3868. 第2题-服务器的编号
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 147
            Accepted: 35
            Difficulty: 5
            
          
          
          
                       所属公司 : 
                              华为
                                
            
                        
              时间 :2025年10月10日(留学生)-非AI方向(通软&嵌软&测试&算法&数据科学)
                              
                      
          
 
- 
                        算法标签>模拟          
 
第2题-服务器的编号
解题思路
我们有 M 台服务器(编号 1..M),N 个任务(编号 1..N)。第 i 个任务给出启动时间 s_i 与执行时间 t_i,不同任务的启动时间两两不同。任务按启动时间发生:
当某任务到来时,所有在该时刻之前或恰好完成的任务会释放其服务器;若有空闲服务器,则该任务立刻占用编号最小的空闲服务器并执行。要求输出编号为 K 的任务在执行时占用的服务器编号。
核心算法:事件模拟 + 两个小根堆(优先队列)
- 
将任务按启动时间
s_i升序排序,同时保留任务原编号i。 - 
维护两个堆:
avail:空闲服务器编号的小根堆(初始放入1..M)。busy:正在运行任务的小根堆,元素为(结束时间, 服务器编号)。
 - 
依次处理每个任务
(s_i, t_i, i):- 先把 
busy中所有结束时间 <= s_i的元素弹出,并把对应服务器放回avail; - 从 
avail弹出最小编号的服务器id,记录ans[i] = id; - 将 
(s_i + t_i, id)压入busy。 
 - 先把 
 - 
最后输出
ans[K]。 
复杂度分析
- 排序:
O(N log N) - 每个任务最多一次入堆/出堆,两类堆的操作均为 
O(log M),合计O(N log M) - 总时间复杂度:
O(N log N + N log M) - 空间复杂度:
O(M + N)(两个堆与答案数组) 
代码实现
Python
import sys
import heapq
def server_of_k(M, tasks, K):
    # tasks: 列表 [(s, t, idx)]
    tasks.sort(key=lambda x: x[0])  # 按启动时间排序
    # 空闲服务器小根堆(编号最小优先)
    avail = list(range(1, M + 1))
    heapq.heapify(avail)
    # 正在运行的任务:(结束时间, 服务器编号)
    busy = []
    # 记录每个原编号任务的分配服务器
    ans = [0] * (len(tasks) + 1)
    for s, t, idx in tasks:
        # 释放所有在 s 之前或恰好 s 时刻完成的任务
        while busy and busy[0][0] <= s:
            end_time, sid = heapq.heappop(busy)
            heapq.heappush(avail, sid)
        # 取出最小编号的空闲服务器
        sid = heapq.heappop(avail)
        ans[idx] = sid
        # 压入该任务的结束事件
        heapq.heappush(busy, (s + t, sid))
    return ans[K]
def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    M = int(next(it)); N = int(next(it)); K = int(next(it))
    tasks = []
    for i in range(1, N + 1):
        s = int(next(it)); t = int(next(it))
        tasks.append((s, t, i))
    print(server_of_k(M, tasks, K))
if __name__ == "__main__":
    main()
Java
import java.util.*;
public class Main {
    static int serverOfK(int M, int[][] tasks, int K) {
        // 按启动时间升序
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[0]));
        // 空闲服务器:小根堆(编号最小优先)
        PriorityQueue<Integer> avail = new PriorityQueue<>();
        for (int i = 1; i <= M; i++) avail.offer(i);
        // 正在运行:小根堆(结束时间最小优先)
        // 元素为 int[]{endTime, serverId}
        PriorityQueue<int[]> busy = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int n = tasks.length;
        int[] ans = new int[n + 1]; // 以任务原编号为下标
        for (int[] x : tasks) {
            int s = x[0], t = x[1], idx = x[2];
            // 释放完成的任务(结束时间 <= 当前启动时间)
            while (!busy.isEmpty() && busy.peek()[0] <= s) {
                int[] cur = busy.poll();
                avail.offer(cur[1]);
            }
            // 分配最小编号服务器
            int sid = avail.poll();
            ans[idx] = sid;
            // 加入结束事件
            busy.offer(new int[]{s + t, sid});
        }
        return ans[K];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int K = sc.nextInt();
        // tasks[i] = {start, duration, originalIndex}
        int[][] tasks = new int[N][3];
        for (int i = 0; i < N; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            tasks[i][0] = s;
            tasks[i][1] = t;
            tasks[i][2] = i + 1; // 原编号
        }
        System.out.println(serverOfK(M, tasks, K));
    }
}
C++
#include <bits/stdc++.h>
using namespace std;
int server_of_k(int M, vector<tuple<int,int,int>>& tasks, int K) {
    // 按启动时间排序
    sort(tasks.begin(), tasks.end());
    // 空闲服务器:最小编号优先
    priority_queue<int, vector<int>, greater<int>> avail;
    for (int i = 1; i <= M; ++i) avail.push(i);
    // 正在运行任务:结束时间最小优先,元素 (end, serverId)
    using PII = pair<int,int>;
    priority_queue<PII, vector<PII>, greater<PII>> busy;
    int n = (int)tasks.size();
    vector<int> ans(n + 1, 0); // 原编号 -> 服务器编号
    for (auto &tp : tasks) {
        int s = get<0>(tp), t = get<1>(tp), idx = get<2>(tp);
        // 释放到当前时刻已完成的任务
        while (!busy.empty() && busy.top().first <= s) {
            int sid = busy.top().second;
            busy.pop();
            avail.push(sid);
        }
        // 分配最小编号的空闲服务器
        int sid = avail.top(); avail.pop();
        ans[idx] = sid;
        // 加入结束事件
        busy.push({s + t, sid});
    }
    return ans[K];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N, K;
    if (!(cin >> M >> N >> K)) return 0;
    vector<tuple<int,int,int>> tasks;
    tasks.reserve(N);
    for (int i = 0; i < N; ++i) {
        int s, t;
        cin >> s >> t;
        tasks.emplace_back(s, t, i + 1); // 保存原编号
    }
    cout << server_of_k(M, tasks, K) << "\n";
    return 0;
}
        题目内容
数据中心有 M 个服务器(编号 1−M ),现在 N 个(编号 1−N )需要执行,当一个任务开始执行时,会独占编号最小的空闲服务器,执行完后会立即释放该服多器。任务按照启动时间的先后顺序执行(所有任务的启动时间都不相同)。请返回编号为 K 的任务执行时占用的服务器编号。
输入描述
第一行是用空格分隔的三个整数:M,N,K 分别代表服务器个数,任务数,需要查询的任务编号, 1<=K<=N<=M<=104
接下来 N 行是编号 1−N 的任务信息,每行是用空格分隔的两个整数,分别代表任务的启动时间,执行需要的时间。1<= 启动时间,执行时间 <=105
输出描述
编号为 K 的任务执行时占用的服务器编号
样例1
输入
4 3 2
1 2
4 6
3 3
输出
2
说明
编号为 1 的任务(启动时间为 1 )占用 1 号服务器
编号为 3 的任务(启动时间为 3 )执行时,编号为 1 的任务已经执行完,1 号服务器空闲,所以占用 1 号服务器
编号为 2 的任务(启动时间为 4 )执行时,编号为 3 的任务还没有执行完,所以占用 2 号服务器
样例2
输入
2 1 1
1 5
输出
1
说明
只有 1 个任务,占用 1 号服务器