题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
java 代码
// package F20170902;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
ArrayList<Teacher> listTeacher = new ArrayList<>();
ArrayList<Integer> listKey = new ArrayList<>();
int arr[] = new int[N];
for(int i=0;i<N;i++) {
arr[i] = i+1;
}
for(int i=0;i<K;i++) {
Teacher t = new Teacher(sc.nextInt(),sc.nextInt(),sc.nextInt());
listTeacher.add(t);
}
int time = 1;
while(time<=maxTime(listTeacher)) {
returnKey(time,listTeacher,arr,listKey);
borrowKey(time,listTeacher,arr);
time++;
}
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
sc.close();
}
public static void returnKey(int time,ArrayList<Teacher> listTeacher,
int arr[],ArrayList<Integer> listKey) {
listKey.clear();
//要还的钥匙找到了
for(int i=0;i<listTeacher.size();i++) {
if(listTeacher.get(i).e==time) {
listKey.add(listTeacher.get(i).w);
}
}
//排序要还的钥匙
for(int i=0;i<listKey.size()-1;i++) {
for(int j=0;j<listKey.size()-i-1;j++) {
if(listKey.get(j)>listKey.get(j+1)) {
int temp = listKey.get(j);
listKey.set(j, listKey.get(j+1));
listKey.set(j+1, temp);
}
}
}
//还钥匙
if(listKey.isEmpty()) {
return ;
}
for(int i=0,j=0;i<arr.length;i++) {
if(arr[i]==0) {
arr[i] = listKey.get(j);
if(j+1==listKey.size()) {
break;
}
else {
j++;
}
}
}
}
public static void borrowKey(int time,ArrayList<Teacher> listTeacher,int arr[]) {
for(int i=0;i<listTeacher.size();i++) {
if(time==listTeacher.get(i).s) {
for(int j=0;j<arr.length;j++) {
if(listTeacher.get(i).w==arr[j]) {
arr[j] = 0;
break;
}
}
}
}
}
//循环次数
public static int maxTime(ArrayList<Teacher> listTeacher) {
int ans = 0;
for(int i=0;i<listTeacher.size();i++) {
ans = Math.max(ans, listTeacher.get(i).e);
}
return ans;
}
}
//数据
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.e = s+c;
}
}