[BOJ 2473，Python] 三种解决方案

问题链接

boj 2473

分类

分段、排序、两个指针

描述

这是经典的双指针问题的稍高级版本。

当我第一次解这道题时，我认为一定有不同的解法，因为我必须把三种解法结合起来，所以我出乎意料地没有使用精确法，导致实际解题速度减慢。

这个问题最重要的一点是，解的总数必须在 5000 个以内。如果没有这个条件，这个问题就永远无法及时解决......可惜我一开始没有注意到这个条件，导致我一直在寻找其他解法。

因此，这个问题的解决方案可以表述如下。

排序→固定一个解→对其余解使用双指针算法，与该解求和，得到最接近 0 的解→当所有解都遍历或到达 0 时停止

求解代码

# 세 용액

import sys

input = sys.stdin.readline

solution_number = int(input())
solution_list = list(map(int, input().split()))

solution_list.sort()
characteristic_value = 3000000000

for idx in range(solution_number):

    pointer_1 = 0
    pointer_2 = solution_number - 1

    while pointer_1 < pointer_2:

        if pointer_1 == idx:
            pointer_1 += 1
        if pointer_2 == idx:
            pointer_2 -= 1

        if pointer_1 >= pointer_2:
            break

        now_value = sum([solution_list[idx], solution_list[pointer_1], solution_list[pointer_2]])

        if abs(now_value) < characteristic_value:
            characteristic_value = abs(now_value)
            result = [solution_list[idx], solution_list[pointer_1], solution_list[pointer_2]]

            if not characteristic_value:
                break

        if now_value < 0:
            pointer_1 += 1
        elif now_value > 0:
            pointer_2 -= 1

    if not characteristic_value:
        break

result.sort()

print(*result)