TopCoder练习:OptimalQueue (SRM 297 Div1 Easy)

问题:某银行设置tellCount台ATM机器,每次机器服务一位客户需要serviceTime分钟。在ATM开始服务以前,就有客户等待。如果有一个n位客户,他们分别在ATM开始服务之前的等待时间可以表示成一个序列{ t1, t2, t3, …, tn }。ATM开始服务之后需要尽快处理客户请求,求这种情况下需要最短多少时间可以处理完所有客户请求。

等级:简单

解答:ATM机器可以同时服务tellCount位客户。从排队等待时间最长的客户开始服务,可以保证在最短时间内处理完所有客户请求。所以,对等待时间序列排序,每次取出tellCount个元素中的最大值并且加上serviceTime就是本轮客户一共花费的时间,依次计算处理每一轮客户请求所花费的时间。返回这些结果中的最大值。

import java.util.Arrays;

public class OptimalQueue {
    public int minWaitingTime(int[] clientArrivals,
			      int tellerCount,
			      int serviceTime) {
	int[] shadow = Arrays.copyOf(clientArrivals, clientArrivals.length);

	for (int i = 0; i < shadow.length; i++) shadow[i] *= -1;
	Arrays.sort(shadow);
	for (int i = 0; i < shadow.length; i++) shadow[i] *= -1;

	for (int i = 0; i < shadow.length; i++)
	    ret = Math.max(ret, shadow[i] + (i / tellerCount + 1) * serviceTime);

	return ret;
    }
}

发表评论