题解

题面描述

公司拥有 $N$ 个会议室，每个会议室的容量各不相同。员工通过会议管理系统提交会议需求，每个需求包含参会人数、开始时间和会议时长。由于会议室的数量和容量有限，有些会议可能无法被安排。需要输出每天无法被正常安排的会议次数以及无法参会的总人次。

分配会议室的原则：

1. 按照会议需求的提交顺序依次处理。
2. 被安排的会议室容量必须满足参会人数的要求（即会议室容量 ≥ 参会人数）。
3. 优先选择容量最接近参会人数的会议室。
4. 会议占用会议室的时间区间为 [开始时间, 开始时间 + 时长)。
5. 为了保证会议室的利用率，同一场会议可以在中途更换会议室。

思路

首先，将所有会议室按容量从小到大排序，以便优先选择最适合的会议室。然后，逐一处理每个会议需求，检查每个会议室是否有足够的容量且在会议的时间段内空闲。如果找到符合条件的会议室，就将会议安排进去并记录其时间段；如果没有合适的会议室，则统计该会议为无法安排，并累加无法参会的人数。最终，通过遍历所有会议需求，计算出无法安排的会议次数和总无法参会的人次，并输出结果。

1. 会议室排序：首先对所有会议室按容量从小到大排序。这样在分配会议室时，可以优先选择容量最接近参会人数的会议室。

2. 会议室日程管理：为每个会议室维护一个日程表，记录其已经安排的会议时间段。由于会议的开始时间和结束时间可能是任意的，我们需要检查一个会议是否可以被安排到某个会议室中，方法是确保该会议的时间段不与会议室中已安排的任何会议时间段重叠。

3. 会议分配：

   • 按照会议需求的提交顺序依次处理每一个会议。
   • 对于每一个会议，遍历排序后的会议室列表，找到第一个容量满足要求且在会议时间段内空闲的会议室。
   • 如果找到合适的会议室，将该会议分配给该会议室，并更新会议室的日程表。
   • 如果没有找到合适的会议室，记录该会议为无法安排，并累加无法参会的人次。

4. 输出结果：最后输出无法被安排的会议次数以及无法参会的总人次。

cpp

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

int main(){
    int N;
    cin >> N; // 输入会议室数量
    vector<int> capacities(N);
    for(auto &x: capacities) cin >> x; // 输入每个会议室的容量
    
    // 按容量从小到大排序会议室
    sort(capacities.begin(), capacities.end());
    
    int M;
    cin >> M; // 输入会议需求数量
    
    struct Meeting {
        int participants;
        int start;
        int duration;
    };
    vector<Meeting> meetings(M);
    for(int i=0;i<M;i++) {
        cin >> meetings[i].participants >> meetings[i].start >> meetings[i].duration;
    }
    
    // 初始化每个会议室的占用情况，时间点从1到200
    vector<vector<bool>> room_schedules(N, vector<bool>(201, false));
    
    int unassigned_count = 0; // 无法安排的会议次数
    int unassigned_people = 0; // 无法参会的总人次
    
    for(auto &meeting: meetings){
        int participants = meeting.participants;
        int start = meeting.start;
        int end = meeting.start + meeting.duration;
        bool can_assign = true;
        vector<int> assigned_rooms;
        
        for(int t = start; t < end; t++){
            bool room_found = false;
            for(int room_idx = 0; room_idx < N; room_idx++){
                if(capacities[room_idx] >= participants && !room_schedules[room_idx][t]){
                    room_schedules[room_idx][t] = true;
                    assigned_rooms.push_back(room_idx);
                    room_found = true;
                    break;
                }
            }
            if(!room_found){
                can_assign = false;
                break;
            }
        }
        
        if(!can_assign){
            // 回滚之前的分配
            for(int i = 0; i < assigned_rooms.size(); i++){
                int t = start + i;
                room_schedules[assigned_rooms[i]][t] = false;
            }
            unassigned_count++;
            unassigned_people += participants;
        }
    }
    
    cout << unassigned_count << " " << unassigned_people;
}

python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx +=1  # 读取会议室数量
    capacities = list(map(int, data[idx:idx+N])); idx +=N  # 读取每个会议室的容量
    rooms = sorted(capacities)  # 按容量从小到大排序会议室
    
    M = int(data[idx]); idx +=1  # 读取会议需求数量
    meetings = []
    for _ in range(M):
        participants = int(data[idx]); idx +=1
        start = int(data[idx]); idx +=1
        duration = int(data[idx]); idx +=1
        meetings.append( (participants, start, duration) )  # 记录每个会议的需求
    
    # 初始化每个会议室的占用情况，时间点从1到200
    room_schedules = [ [False]*201 for _ in range(N) ]
    
    unassigned_count = 0  # 无法安排的会议次数
    unassigned_people = 0  # 无法参会的总人次
    
    for meeting in meetings:
        participants, start, duration = meeting
        end = start + duration  # 会议结束时间
        can_assign = True
        assigned_rooms = []
        
        # 对会议的每个时间点进行分配
        for t in range(start, end):
            room_found = False
            for room_idx, cap in enumerate(rooms):
                if cap >= participants and not room_schedules[room_idx][t]:
                    # 分配该会议室
                    room_schedules[room_idx][t] = True
                    assigned_rooms.append(room_idx)
                    room_found = True
                    break
            if not room_found:
                can_assign = False
                break  # 当前时间点无法分配，终止分配
        
        if not can_assign:
            # 回滚之前分配的会议室占用
            for i in range(len(assigned_rooms)):
                t = start + i
                room_schedules[assigned_rooms[i]][t] = False
            # 统计无法安排
            unassigned_count +=1
            unassigned_people += participants
    
    print(f"{unassigned_count} {unassigned_people}")

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        
        // 读取会议室数量 N
        line = br.readLine();
        int N = Integer.parseInt(line.trim());
        
        // 读取每个会议室的容量
        line = br.readLine();
        String[] capStr = line.trim().split("\\s+");
        List<Integer> capacities = new ArrayList<>();
        for(int i=0;i<N;i++) {
            capacities.add(Integer.parseInt(capStr[i]));
        }
        
        // 按容量从小到大排序会议室
        Collections.sort(capacities);
        
        // 读取会议需求数量 M
        line = br.readLine();
        int M = Integer.parseInt(line.trim());
        
        // 初始化每个会议室的占用情况，时间点从1到200
        boolean[][] room_schedules = new boolean[N][201];
        
        int unassigned_count = 0; // 无法安排的会议次数
        int unassigned_people = 0; // 无法参会的总人次
        
        // 逐个处理会议需求
        for(int i=0;i<M;i++){
            line = br.readLine();
            String[] parts = line.trim().split("\\s+");
            int participants = Integer.parseInt(parts[0]); // 参会人数
            int start = Integer.parseInt(parts[1]);        // 会议开始时间
            int duration = Integer.parseInt(parts[2]);     // 会议时长
            int end = start + duration;                     // 计算会议结束时间
            boolean can_assign = true;
            List<Integer> assigned_rooms = new ArrayList<>();
            
            for(int t=start; t<end; t++){
                boolean room_found = false;
                for(int room_idx=0; room_idx<N; room_idx++){
                    if(capacities.get(room_idx) >= participants && !room_schedules[room_idx][t]){
                        room_schedules[room_idx][t] = true;
                        assigned_rooms.add(room_idx);
                        room_found = true;
                        break;
                    }
                }
                if(!room_found){
                    can_assign = false;
                    break;
                }
            }
            
            if(!can_assign){
                // 回滚之前的分配
                for(int j=0; j<assigned_rooms.size(); j++){
                    int t = start + j;
                    room_schedules[assigned_rooms.get(j)][t] = false;
                }
                unassigned_count++;
                unassigned_people += participants;
            }
        }
        // 输出结果
        System.out.println(unassigned_count + " " + unassigned_people);
    }
}

题目内容

在一个公司里有 $N$ 个会议室，会议室容量各不相同，员工通过会议管理系统提交会议需求，会议需求包括参会人数，开始时间，会议时长。

由于会议室容量和数量限制，有些会议不能被正常安排，要求输出每天不能被正常安排的会议个数和不能参加会议的总人次。

分配会议室原则如下:

1、按会议需求提交顺序依次处理会议室分配需求。

2、所安排会议室的容量要满足参会人数要求。即会议室容量>=参会人数。

3、优先安排使用容量最接近参会人数的会议室。

4、会议占用会议室的时间段包括会议的开始的时间点，不包括结束的时间点。比如一场时长为 $2$ 的会议在时间点 $2$ 开始，其会议时间区间为 $[2,4]$。

5、为保证会议室利用率，对同一场会议，中途可以变更会议室

输入描述

输入分多行数据输入

第 $1$ 行有 $1$ 个数中 $N$ ，表示会议室的数量。数字区间为 $[1,20]$ ，为整数。

第 $2$ 行为用空格隔开的 $N$ 个数字，依次表示各个会议室可容纳的最大人数。数字区间为 $[5,50]$，为整数。

第 $3$ 行为一个数字 $M$ ，表示有 $M$ 个会议需求申请。数字区间为 $[0,200]$

从 $4$ 行开始的 $M$ 行数据，每一行表示一个会议需求申请，顺序为需求提交的顺序。每行数据为空格分开的 $3$ 个数字，$3$ 个数字依次为参会人数，会议开始时间点，会议时长。数字区间均为 $[1,200]$ ，均为整数。

输出描述

输出为空格分开的两个数字。依次为不能被安排的会议次数，不能正常参会的人次。

样例1

输入

5
20 5 10 30 20
6
3 5 8
3 5 8
3 5 8
3 5 8
3 5 8
3 5 8

输出

1 3

说明

在时间点 $5$ ，容量 >= $3$ 的会议室被占用了 $5$ 个。有 $1$ 场会议室无法被安排，$3$ 人无法参会。

样例2

输入

5
20 5 10 30 20
4
30 5 8
30 5 8
30 5 8
30 5 8

输出

3 90

说明

在时间点 $5$ ，容量 >= $30$ 的会议室被占用，有 $3$ 场会议无法被安排，有 $90$ 人无法参会。