玄关求助(Python
查看原帖
玄关求助(Python
920098
Jiuweixiansheng楼主2024/2/23 11:26

只有最后一个AC,求大佬帮忙看看

from sys import stdin
from queue import PriorityQueue
n = int(stdin.readline().strip())
sex = list(stdin.readline().strip())
num = list(map(int, stdin.readline().split()))
def dance_pairs(n, sex, skill):
    # 初始化优先队列和结果列表
    pq = PriorityQueue()
    results = []

    # 填充初始队列
    for i in range(n - 1):
        if sex[i] != sex[i + 1]:
            pq.put((abs(skill[i] - skill[i + 1]), i, i + 1))
    
    # 已出列的人员标记
    out = [False] * n

    while not pq.empty():
        _, left, right = pq.get()
        # 检查当前对是否已经出列
        if out[left] or out[right]:
            continue
        # 记录结果
        results.append((left + 1, right + 1))  # 转换为从1开始的编号
        out[left] = out[right] = True  # 标记为出列
        # 检查是否可以形成新的配对
        if left > 0 and not out[left - 1] and right < n - 1 and not out[right + 1] and sex[left - 1] != sex[right + 1]:
            pq.put((abs(skill[left - 1] - skill[right + 1]), left - 1, right + 1))
    
    return results

# 示例
pairs = dance_pairs(n, sex, num)
print(len(pairs))
for pair in pairs:
    print(pair[0], pair[1])


2024/2/23 11:26
加载中...