AcWing 1494. 银行排队(Java)
原题链接
中等
作者:
码海泛舟
,
2020-07-16 09:00:25
,
所有人可见
,
阅读 682
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
static int N = 10010, M = 110;
static int n, m;
static Person[] p = new Person[N];//存储所有的个人记录
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for (int i = 0; i < n; i++) {
int h, m, s, service_time;
String[] s2 = br.readLine().split(" ");
service_time = Integer.parseInt(s2[1]);
String[] s3 = s2[0].split(":");
h = Integer.parseInt(s3[0]);
m = Integer.parseInt(s3[1]);
s = Integer.parseInt(s3[2]);
service_time = Math.min(service_time, 60);//最多服务60分钟
//转化为秒
p[i] = new Person(h * 3600 + m * 60 + s, service_time * 60);
}
//按照到达时间升序排序
Arrays.sort(p, 0, n, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.arrive_time - o2.arrive_time;
}
});
//存储m个窗口的结束时刻(或者说是可用的时刻)
PriorityQueue<Integer> q = new PriorityQueue();
for (int i = 0; i < m; i++) {
q.add(8 * 3600);//8点,转为秒数
}
int sum = 0;//总共等待时间
int cnt = 0;//享受到服务的人数
for (int i = 0; i < n; i++) {
int w = q.poll();
if (p[i].arrive_time > 17 * 3600) break;//该同志及后面的人木得服务
//该同志开始享受服务的时间
int start_time = Math.max(p[i].arrive_time, w);
sum += start_time - p[i].arrive_time;
cnt++;
//更新该窗口的结束时刻
q.add(start_time + p[i].service_time);
}
System.out.printf("%.1f\n", (double)sum / cnt / 60);//我们按秒计算的,转为分钟
}
}
class Person {
int arrive_time;//到达时间,秒
int service_time;//服务时间,秒
public Person(int arrive_time, int service_time) {
this.arrive_time = arrive_time;
this.service_time = service_time;
}
}