AcWing 1494. 银行排队-java-优先队列(堆)
原题链接
中等
作者:
Astarion
,
2021-03-08 17:26:19
,
所有人可见
,
阅读 484
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
class Main {
static int ST = 8 * 3600;
static int ET = 17 * 3600;
static int MP = 3600;
static class Client implements Comparable<Client> {
int at, p;
public Client(int at, int p) {
this.at = at;
this.p = p;
}
@Override
public int compareTo(Client o) {
return this.at - o.at;
}
}
static int getTime(String ts) {
String[] s = ts.split(":");
return Integer.parseInt(s[0]) * 3600 + Integer.parseInt(s[1]) * 60 + Integer.parseInt(s[2]);
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
OutputStreamWriter osw = new OutputStreamWriter(System.out);
BufferedWriter out = new BufferedWriter(osw);
String[] strs = in.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int k = Integer.parseInt(strs[1]);
int tn = 0;
List<Client> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
strs = in.readLine().split(" ");
int time = getTime(strs[0]);
if (time > ET) continue;
Client c = new Client(time, Math.min(Integer.parseInt(strs[1]) * 60, MP));
list.add(c);
tn++;
}
Collections.sort(list);
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < k; i++) queue.add(ST);
int cnt = 0;
for (int i = 0; i < tn; i++) {
int st = queue.poll();
st = Math.max(st, list.get(i).at);
cnt += st - list.get(i).at;
int et = st + list.get(i).p;
queue.add(et);
}
out.write(String.format("%.1f", (double) cnt / tn / 60));
in.close();
isr.close();
out.flush();
out.close();
osw.close();
}
}