为了促进学校男女生之间的交流，学校组织了一个“周末共舞”活动，男生和女生分别排队等待入场。每一首新曲开始，舞池中的同学都会离开场地，正在排队的同学中男生女生从队头进入相同数量，并且尽可能多的同学搭配成舞伴一起入场。每一位同学只跳舞一首曲子的长度，每首曲子长度不同。到最后一首曲子，还未跳过舞的同学们会都进入场地一起跳舞。 因为迟到的同学会给舞会正常进行带来麻烦，为了补偿等待迟到同学造成的时间损失，认为晚于最后一曲开始时间到达的同学的等待时间为负数，即迟到时间的相反数。 请输出男生队伍和女生队伍的平均等待时间分别是多少。 输入格式 第一行：N首曲目（N<100000） 第2行：每一首曲子的长度li 第3行：整个过程将有M个人进入队列(M<1000000) 第4~N+3行：每一行包含每一位到达同学的信息si，第一个数字代表性比：1-男，2-女；第二个数字代表到达时间ti，其中数字0视为第一首乐曲开始时恰好进入，无等待时间。到达时间不会晚于第n首曲目开始的时间。 输出格式 两个两位小数，为所有男生、所有女生的平均等待时间.

这道题可以使用队列来模拟男生和女生排队的过程，每当一首新曲开始，就将队头的男生和女生一起出队，并计算他们的等待时间。搭配成舞伴的同学入场，没有搭配成舞伴的同学继续排队。在最后一首曲子开始前到达的同学可以得到负的等待时间，也要计算在平均等待时间中。

下面是 Python 的实现代码：

n = int(input().strip())
lengths = list(map(int, input().strip().split()))
m = int(input().strip())

# 男生和女生分别用队列来保存
male_q, female_q = [], []
# 记录男生和女生的总等待时间以及到达的人数
male_wait, male_count, female_wait, female_count = 0, 0, 0, 0
# 记录当前时间
time = 0

for i in range(m):
    gender, arrival_time = map(int, input().strip().split())
    if gender == 1:  # 男生
        male_q.append(arrival_time)
    else:  # 女生
        female_q.append(arrival_time)
    
    while male_q and female_q:
        male_arrival = male_q.pop(0)
        female_arrival = female_q.pop(0)
        wait_time = time - max(male_arrival, female_arrival)
        if wait_time > 0:  # 计算等待时间
            male_wait += wait_time
            female_wait += wait_time
            male_count += 1
            female_count += 1
        time += lengths[i]
    
    # 处理最后一首曲子之前到达的同学
    if i == n - 1:
        while male_q:
            male_wait += -male_q.pop(0)
            male_count += 1
        while female_q:
            female_wait += -female_q.pop(0)
            female_count += 1

# 计算平均等待时间
male_avg_wait = male_wait / male_count if male_count > 0 else 0
female_avg_wait = female_wait / female_count if female_count > 0 else 0

print("{:.2f} {:.2f}".format(male_avg_wait, female_avg_wait))

时间复杂度为 $O(mn)$，可以通过本题。