指向挑战的链接可以找到here
问题陈述 Tieu拥有一家比萨饼店,他以自己的方式经营。在一家普通的餐馆里,顾客是按照先到先得的原则来服务的,而Tieu只是将顾客的平均等候时间降到最低。所以他可以决定谁先被服务,不管一个人迟早会来。 不同种类的比萨饼需要不同的时间烹饪。而且,一旦他开始做比萨饼,他就不能再做一个比萨饼,直到第一个比萨饼完全煮熟。假设我们有三个顾客,分别是t=0,t=1,& t=2,他们做比萨饼所需的时间分别是3、9和6。如果Tieu采用先到先得的规则,那么三个顾客的等待时间分别为3、11和16。这种情况下的平均等待时间是(3 + 11 + 16) /3= 10。这不是一个优化的解决方案。在时间t=3为第一位客户服务之后,Tieu可以选择为第三位客户服务。在此情况下,轮候时间分别为3、7及17。因此,平均等待时间为(3 +7+ 17) /3= 9。 帮助Tieu达到最低平均等待时间。为了简单起见,只需找到最小平均等待时间的整数部分即可。 输入格式 第一行包含一个整数N,即客户数。在接下来的N条线中,第1条线包含两个分隔的数字Ti和Li。时间是你的顾客点披萨的时候,而李是煮披萨所需要的时间。输出格式 显示最小平均等待时间的整数部分。 约束 1≤N≤10^5 0≤Ti≤10^9 1≤Li≤10^9 Note 等待时间计算为顾客订购比萨饼的时间(他们进入商店的时间)和服务时间之间的差异。 库克不知道未来的订单。
我已经干了好几个小时了。
我很确定我的问题与我增加总等待时间的方式有关。
任何帮助都将不胜感激。
代码:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
MinimumAverageWaitingTime mawt = new MinimumAverageWaitingTime();
while(n-- > 0) mawt.insert(s.nextLong(), s.nextLong());
System.out.print(mawt.calculateAverageWaitingTime());
}
}
class MinimumAverageWaitingTime {
private PriorityQueue<e_time_p_time> incomingOrders = new PriorityQueue<>(10, new Comparator<e_time_p_time>(){
//Order by the customerWaitTime ASC
@Override public int compare(e_time_p_time w, e_time_p_time w1) {
return (int) (w.entryTime - w1.entryTime);
}
});
private PriorityQueue<e_time_p_time> awaitingOrders = new PriorityQueue<>(10, new Comparator<e_time_p_time>(){
//Order by the difference between entrytime and pizzaCookTime ASC
@Override public int compare(e_time_p_time w, e_time_p_time w1) {
return (int) (Math.abs(w.entryTime - w.pizzaCookTime) - Math.abs(w1.entryTime - w1.pizzaCookTime));
}
});
private long total = 0l;
public void insert(long customerWaitTime, long pizzaCookTime) {
incomingOrders.add(new e_time_p_time(customerWaitTime, pizzaCookTime));
}
public long calculateAverageWaitingTime() {
int size = incomingOrders.size();
e_time_p_time currentOrder = null;
e_time_p_time laterOrders = null;
while(incomingOrders.size() > 0) {
//Start by getting the customer that has the earliest arrival time (the queue is sorted that way)
currentOrder = incomingOrders.remove();
//Calculate it's waiting time.
total += currentOrder.entryTime + currentOrder.pizzaCookTime;
do {
/*Move all the customers that entered the shop while the current pizza is in the oven
to the awaitingOrders orders queue*/
laterOrders = incomingOrders.remove();
awaitingOrders.add(laterOrders);
} while (currentOrder.pizzaCookTime >= laterOrders.entryTime && incomingOrders.size() > 0);
//Go through awaitingOrders queue and calculate waiting time for the remaining orders
//(The queue is sorted as the difference between entrytime and pizzaCookTime ASC)
while(awaitingOrders.size() > 0) {
e_time_p_time shortestOrder = awaitingOrders.remove();
long waitTimeBeforeCooking = Math.abs((shortestOrder.entryTime + shortestOrder.pizzaCookTime) - currentOrder.entryTime);
total += waitTimeBeforeCooking;
}
}
//It's supposed to be the average time, but first I need the total to be correct, and right now, it's not...
System.out.println("\nTotal waiting time: ");
return total;
}
private static class e_time_p_time {
private long entryTime;
private long pizzaCookTime;
e_time_p_time(long entryTime, long pizzaCookTime) {
this.entryTime = entryTime;
this.pizzaCookTime = pizzaCookTime;
}
}
}发布于 2015-07-03 20:07:29
在此代码中:
do {
/*Move all the customers that entered the shop while the current pizza is in the oven
to the awaitingOrders orders queue*/
laterOrders = incomingOrders.remove();
awaitingOrders.add(laterOrders);
} while (currentOrder.pizzaCookTime >= laterOrders.entryTime && incomingOrders.size() > 0);这里有几件事似乎不对:
https://stackoverflow.com/questions/31213473
复制相似问题