银行取款排队模拟 ,请写程序计算所有客户的平均等待时间。

/**
 * o(n)的解决方法，经测试和标准答案的结果是一样的
 * 模拟银行业务场景：
 * 用一个优先队列保存四个元素，四个元素为正在进行的任务执行完成的时间
 * (优先队列会按照任务结束的时间排序, 从队列取到的第一个任务总是最先完成的那个)
 * 用一个变量保存总的等待时间
 *
 * 先往优先队列放入4个任务，这４个任务的等待时间为０，所以优先队列的４个值为4个任务对应的到达时间和执行时间之和，
 * 再把剩下的任务一个个加入优先队列，对于这个要加入的任务，他的等待时间为优先队列的第一个元素（四个任务中最先完成的任务）
 * 的值减去当前任务的开始时间，所以这个要加入的任务的完成时间为“他的等待时间 + 任务到达时间 +　任务执行时间”
 * 依次遍历完所有的任务，得到最终等待时间
 * @param arrive_time
 * @param process_time
 * @return
 */
private static double solution(int[] arrive_time, int[] process_time) {
    PriorityQueue<Integer> processing = new PriorityQueue<>();
    for (int i = 0; i < 4; i++) {
        processing.add(arrive_time[i] + process_time[i]);
    }

    int totalWaitTime = 0;
    int waitTime;
    for (int i = 4; i < arrive_time.length; i++) {
        waitTime = processing.peek() - arrive_time[i];
        //waitTime为负数时不需要等待
        waitTime = Math.max(waitTime, 0);
        totalWaitTime += waitTime;
        processing.poll();
        processing.add(arrive_time[i] + process_time[i] + waitTime);
    }
    return totalWaitTime * 1.0 / arrive_time.length;
}

	t =arrive_time[0]



	user_num =200



	p =0



	window_num =4



	windows =[(-1, 0)]*window_num # user_id, finish_time, -1 stands for nobody here



	wait_q =[]



	wait_time_sum =0.0



	whilep<user_num: #60*60*24 times at most



	    whilet==arrive_time[p]:



	         wait_q.append(p)



	         p +=1



	    fori inrange(window_num):



	        user_id, finish_time =windows[i]



	        iffinish_time==t:



	            wait_time_sum +=t-process_time[user_id]-arrive_time[user_id]



	            windows[i] =(-1, 0)



	        ifwindows[i][0]==-1:



	            next_user =wait_q.pop(0)



	            windows[i] =(next_user, t+process_time[next_user])



	    t +=1



	printwait_time_sum/len(arrive_time)

OC代码解题

- (void)viewDidLoad {

[super viewDidLoad];

NSArray *arrive_time = @[@1,@2,@3,@4,@4,@8];

NSArray *process_time = @[@50,@20,@11,@25,@30,@40];

if (arrive_time.count < 4) {

NSLog(@"等待时间为:%d",0);

return;

}

NSMutableArray *array = [NSMutableArray array];

for (int i = 0; i < 4; i++) {

NSInteger total = [arrive_time[i] integerValue] + [process_time[i] integerValue];

[array addObject:[NSNumber numberWithInteger:total]];

}

NSInteger totalWaiteTime = 0;

NSInteger waiteTime = 0;

for (int i = 4; i < arrive_time.count; i++) {

NSInteger min = [self fetchMinArray:array];

NSInteger processTime = [array[min] integerValue];

waiteTime = processTime - [arrive_time[i] integerValue];

waiteTime = waiteTime <= 0 ? 0 : waiteTime;

totalWaiteTime +=waiteTime;

array[min] = [NSNumber numberWithInteger:[array[min] integerValue] + [process_time[i] integerValue]];

waiteTime = 0;

}

NSLog(@"等待时间为:%lu",totalWaiteTime/arrive_time.count);

}

- (NSInteger)fetchMinArray:(NSArray *)minArray {

NSInteger min = 0;

for (NSInteger i = 1; i < minArray.count; i++) {

if ([minArray[min] integerValue] > [minArray[i] integerValue]) {

min =  i;

}

}

return min;

}

	arrive_time.push_back(1);