AcWing 127. 任务(Java)
原题链接
困难
作者:
上杉
,
2021-05-04 15:17:41
,
所有人可见
,
阅读 407
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static Machine[] machines;
static Task[] tasks;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] fl = bf.readLine().split(" ");
int N = Integer.parseInt(fl[0]);
int M = Integer.parseInt(fl[1]);
machines = new Machine[N];
tasks = new Task[M];
for (int i = 0; i < N; i++) {
String[] opl = bf.readLine().split(" ");
int time = Integer.parseInt(opl[0]);
int level = Integer.parseInt(opl[1]);
machines[i] = new Machine(time,level);
}
for (int i = 0; i < M; i++) {
String[] opl = bf.readLine().split(" ");
int time = Integer.parseInt(opl[0]);
int level = Integer.parseInt(opl[1]);
tasks[i] = new Task(time,level);
}
Arrays.sort(machines, new Comparator<Machine>() {
@Override
public int compare(Machine o1, Machine o2) {
return o2.time - o1.time;
}
});
Arrays.sort(tasks, new Comparator<Task>() {
@Override
public int compare(Task o1, Task o2) {
if (o1.time == o2.time){
return o2.level - o1.level;
}
return o2.time - o1.time;
}
});
int index = 0;
int count = 0;
long res = 0;
TreeMap<Integer,List<Machine>> canUse = new TreeMap<>();
for (int i = 0; i < M; i++) {
//判断第i个任务
int t = tasks[i].time;
int level = tasks[i].level;
while (index < N && machines[index].time >= t){
List<Machine> list = canUse.get(machines[index].level);
if (list == null){
list = new ArrayList<>();
canUse.put(machines[index].level,list);
}
list.add(machines[index]);
index++;
}
Map.Entry<Integer, List<Machine>> entry = canUse.ceilingEntry(level);
if (entry == null){
continue;
}else {
List<Machine> value = entry.getValue();
if (value.size() == 1){
canUse.remove(entry.getKey());
}else {
value.remove(0);
}
count++;
res += (500 * t + 2 * level);
}
}
System.out.println(count+" "+res);
}
static class Machine implements Comparable<Machine>{
int time;
int level;
public Machine(int time, int level) {
this.time = time;
this.level = level;
}
@Override
public int compareTo(Machine o) {
return level - o.level;
}
}
static class Task{
int time;
int level;
public Task(int time, int level) {
this.time = time;
this.level = level;
}
}
}