201709-2 CCF(Javaコード実装)
4773 ワード
公共の鍵の箱の問題は1つの学校の先生がNつの教室を共用することを説明して、規定によって、すべての鍵はすべて公共の鍵の箱の中に置かなければならなくて、先生は鍵を持って家に帰ることができません.先生は授業の前に、公共の鍵箱から自分の授業の教室の鍵を見つけてドアを開け、授業が終わった後、鍵箱に戻します.鍵箱は全部でN個のフックがあり、左から右に並んで、N個の教室の鍵を掛けるために使われています.一連の鍵には固定された吊り下げ位置はありませんが、鍵には標識があるので、先生たちは鍵を混同しません.鍵を取るたびに、先生たちは自分の必要な鍵を見つけて取り、他の鍵を移動しません.鍵を返すたびに、鍵を返す先生は一番左の空いているフックを見つけて、このフックに鍵を掛けます.複数の先生が鍵を返している場合は、鍵番号の小さい順に返します.同じ時刻に先生が鍵を返したり、先生が鍵を取ったりすると、先生たちはまず鍵を全部返してから取り出します.今日から鍵は番号が小さい順に鍵箱に入っています.K人の先生が授業を受けます.先生一人一人に必要な鍵、授業を始める時間と授業を受ける時間が長いです.授業が終わる時間が鍵を返す時間だとしたら、最終的に鍵箱の中の鍵の順番はどうですか.入力フォーマット入力の最初の行は2つの整数N,Kを含む.次のK行は、1行3つの整数w,s,cで、1人の先生が使う鍵番号、授業開始時間、授業時間をそれぞれ表します.複数の先生が同じ鍵を使っているかもしれませんが、先生が鍵を使っている時間は重複しません.入力データが入力フォーマットを満たすことを保証し、データの合法性を検査する必要はありません.出力フォーマットは、N個の整数を含む1行を出力し、隣接する整数間を1つのスペースで区切って、各フックに掛けられた鍵番号を順次表す.サンプル入力5 2 4 3 3 2 7サンプル出力1 4 3 2 5サンプルは、1番目の先生が時刻3から4番教室の鍵を使用し、3単位時間を使用することを説明するので、時刻6で鍵を返す.2番目の先生は時刻2から鍵を使い、7単位の時間を使うので、時刻9で鍵を返します.各キーポイント後のキーの状態は以下の通りです.(Xは空を示す):時刻2後は1 X 345、時刻3後は1 X 3 X 5、時刻6後は143 X 5、時刻9後は14325である.サンプル入力5 7 1 14 3 12 1 15 12 12 12 7 20 3 18 12 4 21 19 5 30サンプル出力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であった.私の考え:私の考えではありませんて、私の考えは间违っていて、私は私の愚かな方法を尽くして长い间书いて、同じく成功を実现していませんて、もし単纯な配列を设けて书くならば、条件は多くて、仕方がなくてすべてそろって、だから私はネット上の大神の书き方を参考にしてここで大神のウェブサイトを贴り付けました:https://blog.csdn.net/zz2013215/article/details/78561461?reload大神のコードの书くのはとても完璧で、多くこのような大神が私の学友であることができることを望んで、このように私は私のccfを心配しないで大神のブログを见ることができて、しかし大神のコードの上で注釈が少なくて、私はコードの上で多くの注釈をプラスして、分からない小さいかわいいは私のコードの注釈を见ることができて、できないのは私に私信を出す主要なステップは実は2つです:1、鍵を返す2、鍵を借りるのは先生の属性があり、判断する条件が多いので大神(原作者をオオカミと呼ぶ)には2つの集合が設けられており、集合は自分で定義したタイプのデータを格納することができる.ここでは1つの教師クラスを設定し、教師が持っている属性をクラスに書き、1つの教師の集合を設定し、鍵を借りるたびに集合中の教師の属性を巡り、もう1つの鍵の集合を設定し、教師が鍵を返すときもし何人かの先生が同じ時間に鍵を返して、鍵の番号の大きさによって鍵を返すならば、それではこのいくつかの先生の鍵の番号をこの集合の中に置くことができて、それからこの集合に対して順序をつけて、大神は簡単な泡の順序を使って、それから順番に鍵を返すことができます.また最大時間を定義し、最後の教師が鍵を返した後に終了します.キー配列の配列を出力します.ccfの上で100分のコード、原作者のコードとそっくりで、人の打ったことによって、私はこのような問題をすることができません:
import java.util.ArrayList;
import java.util.Scanner;
class Teacher {
int w;//
int s;//
int c;//
int e;//
public Teacher(int w, int s, int c) {
this.w = w;
this.s = s;
this.c = c;
this.e = this.s + this.c;
}
public int getW() {
return w;
}
public int getS() {
return s;
}
public int getC() {
return c;
}
public int getE() {
return e;
}
}
public class YaoShi2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
ArrayList al = new ArrayList();//
ArrayList key = new ArrayList();//
int time = 1;
int n = in.nextInt();// n
int k = in.nextInt();// k
int[] arr = new int[n];//
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
// ( , , )
for (int i = 1; i <= k; i++) {
Teacher t = new Teacher(in.nextInt(), in.nextInt(), in.nextInt());
al.add(t);
}
//
while (time <= maxTime(al)) {
returnKey(time, al, arr, key);
borrowKey(time, al, arr);
time++;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
//
public static void borrowKey(int time, ArrayList al, int[] arr) {
for (int i = 0; i < al.size(); i++) {
if (time == al.get(i).getS()) {//
for (int j = 0; j < arr.length; j++) {//
if (al.get(i).getW() == arr[j]) {//
arr[j] = 0;// 0
break;
}
}
}
}
}
//
public static void returnKey(int time, ArrayList al, int[] arr,
ArrayList key) {
key.clear();//
for (int i = 0; i < al.size(); i++) {
if (time == al.get(i).getE()) {
key.add(al.get(i).getW());
}
}
if (key.isEmpty()) {
return;//
} else {//
for (int i = 0; i < key.size() - 1; i++) {
for (int j = 0; j < key.size() - 1 - i; j++) {
if (key.get(j) > key.get(j + 1)) {
int tmp = key.get(j);
// key.get(i)=key.get(j);// ArrayList
key.set(j, key.get(j + 1));
key.set(j + 1, tmp);
}
}
}
for (int i = 0, j = 0; i < arr.length; i++) {
if (arr[i] == 0) {
arr[i] = key.get(j);
if (j == key.size() - 1) {
break;
} else {
j++;
}
}
}
}
}
public static int maxTime(ArrayList al) {
int temp = 0;
for (int i = 0; i < al.size(); i++) {
if (al.get(i).getE() > temp) {
temp = al.get(i).getE();
}
}
return temp;// temp
}
}