人工智能deepseek最厉害

解题思路:

注意事项:

参考代码:import math

import heapq

import sys

def min_sprinklers(n, L, W, sprinklers):

    intervals = []

    W_half = W / 2

    for pos, r in sprinklers:

        if r < W_half:

            continue  # 喷头无法覆盖整个宽度

        dx = math.sqrt(r**2 - W_half**2)

        start = max(0, pos - dx)

        end = min(L, pos + dx)

        intervals.append((start, end))

    # 按照起始位置排序

    intervals.sort()

    count = 0

    current_end = 0

    i = 0

    n = len(intervals)

    heap = []

    while current_end < L:

        # 将所有覆盖当前区域的区间加入堆

        while i < n and intervals[i][0] <= current_end:

            heapq.heappush(heap, -intervals[i][1])  # 使用负数模拟最大堆

            i += 1

        if not heap:

            return -1  # 没有可用的区间，无法覆盖

        # 选择覆盖最远的区间

        max_end = -heapq.heappop(heap)

        if max_end <= current_end:

            return -1  # 无法覆盖当前区域

        current_end = max_end

        count += 1

    return count

def main():

    input = sys.stdin.read().split()

    ptr = 0

    T = int(input[ptr])

    ptr += 1

    for _ in range(T):

        n = int(input[ptr])

        L = int(input[ptr + 1])

        W = int(input[ptr + 2])

        ptr += 3

        sprinklers = []

        for _ in range(n):

            pos = int(input[ptr])

            r = int(input[ptr + 1])

            sprinklers.append((pos, r))

            ptr += 2

        result = min_sprinklers(n, L, W, sprinklers)

        print(result)

if __name__ == "__main__":

    main()