解题思路
这是一个课程冲突检测问题。关键点如下:
- 每节课有两个信息:上课时间和课程代码
- 上课时间由两位数表示:
- 第一位(0-4)表示周一至周五
- 第二位(0-9)表示第几节课
- 需要检测是否存在时间冲突的课程
解题思路:
- 使用数组或哈希表记录每个时间段的课程
- 如果同一时间段出现多个课程,则存在冲突
- 按照时间顺序输出所有冲突的课程信息
代码
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> subject[50]; // 存储每个时间段的课程
vector<int> conflicts; // 存储发生冲突的时间
// 读取课程信息
for (int i = 0; i < n; i++) {
int time;
string code;
cin >> time >> code;
// 如果该时间已有课程,记录冲突
if (subject[time].size() == 1) {
conflicts.push_back(time);
}
subject[time].push_back(code);
}
// 输出结果
if (conflicts.empty()) {
cout << "YES" << endl;
} else {
// 按时间排序
sort(conflicts.begin(), conflicts.end());
// 输出冲突信息
for (int time : conflicts) {
printf("%02d", time); // 输出时间,保证两位数
for (const string& code : subject[time]) {
cout << " " << code;
}
cout << endl;
}
}
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<String>[] subject = new ArrayList[50];
ArrayList<Integer> conflicts = new ArrayList<>();
// 初始化数组
for (int i = 0; i < 50; i++) {
subject[i] = new ArrayList<>();
}
// 读取课程信息
for (int i = 0; i < n; i++) {
int time = sc.nextInt();
String code = sc.next();
if (subject[time].size() == 1) {
conflicts.add(time);
}
subject[time].add(code);
}
// 输出结果
if (conflicts.isEmpty()) {
System.out.println("YES");
} else {
Collections.sort(conflicts);
for (int time : conflicts) {
System.out.printf("%02d", time);
for (String code : subject[time]) {
System.out.print(" " + code);
}
System.out.println();
}
}
}
}
n = int(input())
subject = [[] for _ in range(50)] # 存储每个时间段的课程
conflicts = [] # 存储发生冲突的时间
# 读取课程信息
for _ in range(n):
time, code = input().split()
time = int(time)
# 如果该时间已有课程,记录冲突
if len(subject[time]) == 1:
conflicts.append(time)
subject[time].append(code)
# 输出结果
if not conflicts:
print("YES")
else:
# 按时间排序
conflicts.sort()
# 输出冲突信息
for time in conflicts:
print(f"{time:02d}", end="") # 输出时间,保证两位数
for code in subject[time]:
print(f" {code}", end="")
print()
算法及复杂度
- 算法:哈希表
- 时间复杂度:
- 主要是排序的时间复杂度
- 空间复杂度:
- 需要存储所有课程信息