CCF认证试题 2017-09-02 公共钥匙盒 ----Java实现

问题描述

  有一个学校的老师共用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。

其实本题最核心的部分在于

  1. 对每一时刻进行判断,看看有没有要归还的,如果有,则先将所有要归还的钥匙收集起来,然后按照要求根据钥匙序号从小到大归还;之后再看看有没有要取钥匙的,如果有,则取走钥匙。
  2. 因为题目中有提到 “如果同一时刻既有老师还钥匙又有老师取钥匙,则老师们会先将钥匙全还回去再取出。” 因此对于每一时刻都先进行还操作,再进行取操作,避免出错!
  3. 为方便实现,将还钥匙和取钥匙分别封装成相应方法,评测分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;
	}	
}

总结一下:

  1. 我最大的问题是不懂得怎么进行每个时刻的判断,也就是判断是借钥匙还是还钥匙,刚开始并未想到利用一个简单的计数器即可,真的是特别菜鸡!

  2. 本文是参考了其他大佬的代码之后自己写出来的,并不是抄袭,只是觉得人家的代码封装和排版比较整洁美观,自行模仿,难免有些相似。我所参考的博客原址 (感谢这位大佬!)
    https://blog.csdn.net/ZZ2013215/article/details/78561461

  3. 对于代码部分,大家可以自行修改,比如对于钥匙盒挂钩和所挂钥匙号处理,完全可以用一个一维数组代替,不必封装成一个类;对于要归还的钥匙序列保存也可以用一个一维数组代替,大家可以自行修改!

最后,欢迎各位查阅,若有改进意见,欢迎提出,谢谢大家!

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://vivi.run/archives/ccf-public-keybox