问题描述
有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。
钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。
每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。
今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？
输入格式
输入的第一行包含两个整数N, K。
接下来K行，每行三个整数w, s, c，分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙，但是老师使用钥匙的时间不会重叠。
保证输入数据满足输入格式，你不用检查数据合法性。
输出格式
输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。
样例输入
5 2
4 3 3
2 2 7
样例输出
1 4 3 2 5
样例说明
第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，则在时刻9还钥匙。
每个关键时刻后的钥匙状态如下（X表示空）：
时刻2后为1X345；
时刻3后为1X3X5；
时刻6后为143X5；
时刻9后为14325。
样例输入
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
样例输出
1 2 3 5 4
评测用例规模与约定
对于30%的评测用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30；
对于60%的评测用例，1 ≤ N, K ≤ 50，1 ≤ w ≤ N，1 ≤ s ≤ 300，1 ≤ c ≤ 50；
对于所有评测用例，1 ≤ N, K ≤ 1000，1 ≤ w ≤ N，1 ≤ s ≤ 10000，1 ≤ c ≤ 100。
其实本题最核心的部分在于：
- 对每一时刻进行判断，看看有没有要归还的，如果有，则先将所有要归还的钥匙收集起来，然后按照要求根据钥匙序号从小到大归还；之后再看看有没有要取钥匙的，如果有，则取走钥匙。
- 因为题目中有提到 “如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。” 因此对于每一时刻都先进行还操作，再进行取操作，避免出错！
- 为方便实现，将还钥匙和取钥匙分别封装成相应方法，评测分100，代码如下：
package com.ww.ccf;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* @Encoding: UTF-8
* @author: wangwei
* @Date: 2018年12月6日
* @Description: 题目2：公共钥匙盒
*/
public class SortedKey {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();//n个钥匙挂钩
int k = scn.nextInt();//k个老师
Key[] keys = new Key[n+1];//s钥匙挂钩集
for(int i = 1; i <= n; i++)
keys[i] = new Key(i,i); //s初始化钥匙挂钩序列及其位置上钥匙号(钥匙被取走此挂钩钥匙号置0)
Teacher[] tcrs = new Teacher[k+1];//s教师集合
for(int i = 1; i <= k; i++) {//s读入教师上课信息
tcrs[i] = new Teacher(scn.nextInt(),scn.nextInt(),scn.nextInt());
tcrs[i].endTime = tcrs[i].startTime + tcrs[i].classTime;//算出结束时间
}
int time = 1;//s计时器
ArrayList<Integer> rtnList = new ArrayList<>();//此集合保存时刻time所有要还的钥匙号序列
while(time <= maxTime(tcrs)) {//s所有老师开始上课(借钥匙)下课(还钥匙)
rtnKeys(time,tcrs,keys,rtnList);//先还
brwKeys(time,tcrs,keys);//后借
time++;//计时器自增
}
for (int i = 1; i <= n; i++) {
System.out.print(keys[i].LocValue + " ");
}
scn.close();
}
/**
* 求出所有教师最晚结束时间
* @param tcrs
* @return
*/
public static int maxTime(Teacher[] tcrs) {
int temp = 0;
for(int i = 1; i < tcrs.length; i++)
if(temp < tcrs[i].endTime)
temp = tcrs[i].endTime;
return temp;
}
/**
* 还钥匙
* @param tcrs
* @param keys
* @param rtnList
*/
public static void rtnKeys(int time,Teacher[] tcrs,Key[] keys,ArrayList<Integer> rtnList) {
rtnList.clear();//清空之前所还钥匙序列
for(int i = 1; i < tcrs.length; i++)
if(time == tcrs[i].endTime)//将此时刻所有要还的钥匙号加入集合rtnList
rtnList.add(tcrs[i].keyNum);
if(rtnList.isEmpty()) return;//此时刻没有要还的钥匙
Object[] list = rtnList.toArray();//将容器序列转换为对象数组便于排序
Arrays.sort(list);//按所归还钥匙号从小到大排列
//s下面进行归还钥匙操作
for(int i = 1, j = 0; i < keys.length; i++)
if(0 == keys[i].LocValue) {//s判断哪个挂钩上钥匙不在
keys[i].LocValue = (int)list[j];//整形对象转换为整数值
if(j == list.length - 1) //s钥匙已全部还完
break;
else
j++;
}
}
/**
* 借钥匙
* @param time
* @param tcrs
* @param keys
*/
public static void brwKeys(int time,Teacher[] tcrs,Key[] keys) {
for(int i = 1; i < tcrs.length; i++) {
if(time == tcrs[i].startTime)//找出此时刻要借钥匙(此时刻开始上课)的老师
for(int j = 1; j < keys.length; j++) {//s找到对应钥匙号码所在挂钩位置
if(tcrs[i].keyNum == keys[j].LocValue) {
keys[j].LocValue = 0;//s置零表示借走
break;//不会出现同一时刻多个老师借同一个钥匙情况,直接退出当前循环
}
}
}
}
}
class Key {
int LocNum;//钥匙盒挂钩顺序
int LocValue;//每个挂钩上的钥匙号
public Key(int LocNum, int LocValue) {
this.LocNum = LocNum;
this.LocValue = LocValue;
}
}
class Teacher {
int keyNum;//要使用的钥匙序号
int startTime;//开始时间
int classTime;//上课持续时间
int endTime;//结束时间
public Teacher(int keyNum, int startTime, int classTime) {
this.keyNum = keyNum;
this.startTime = startTime;
this.classTime = classTime;
}
}
总结一下：
-
我最大的问题是不懂得怎么进行每个时刻的判断，也就是判断是借钥匙还是还钥匙，刚开始并未想到利用一个简单的计数器即可，真的是特别菜鸡！
-
本文是参考了其他大佬的代码之后自己写出来的，并不是抄袭，只是觉得人家的代码封装和排版比较整洁美观，自行模仿，难免有些相似。我所参考的博客原址 (感谢这位大佬!)
https://blog.csdn.net/ZZ2013215/article/details/78561461 -
对于代码部分，大家可以自行修改，比如对于钥匙盒挂钩和所挂钥匙号处理，完全可以用一个一维数组代替，不必封装成一个类；对于要归还的钥匙序列保存也可以用一个一维数组代替，大家可以自行修改！
最后，欢迎各位查阅，若有改进意见，欢迎提出，谢谢大家！
