[Two Posters]boj 2470:両溶液

デュアルポート:2種類の溶液(boj 2470)

質問リンク:https://www.acmicpc.net/problem/2470
input:5(リスト数)
:-24-99-1988(リスト番号)
output: -99 98

問題を理解する

2つの溶液の問題は、−10000000〜10000000の間の数字を溶液としてリストに列挙し、そのうち2つの溶液の和が0に最も近い2つの溶液を見つけることである.
例えば、−2|4|−99|−1|98という溶液がある場合、両溶液のフィッティングが最も0に近い2つの数は−99および98である.
全部で100000個のリストがあるとしたら、問題を作りましょう.

方法

ダブルポインタでアクセスしようとするには、基本的に最小と最大の数を見つけます.したがって、1つの数に近づくたびに、最小と最大の数を探すと、時間の複雑さが非常に複雑になります.
したがって、まずソートを使用して、リストを-99|-2|-1|4|98に設定します.
[-99, -2, -1, 4, 98]
次に最小の数-99をL,最大の数98をRとし,2つの数を加算して条件を作って解く.
L = -99
R = 98
私たちが探しているのはLとRの和が0に近いので、L+Rが0であれば、LとRを直接出力します.
if L + R == 0: print(L,R)
L+Rの和が0(負数)未満の場合、Lの数字と現在のRより小さい数(すなわち、Rより小さい候補数)の和は、より小さくなる.
すなわち,現在のLは対応するリストから削除できる.残りのどの数に加算しても、現在のR(98)の和から0が遠ざかるからだ.
elif L + R < 0:
L+=1
同様の理由により、L+Rの和が0より大きい場合、Rは他の数との和を必要としなくなる.つまり、リストから削除することができます.
elif L + R > 0:
R-=1
LとRの数字が同じ数字、あるいはLがRより大きい瞬間にloopから出ればいいのです.次に、2つの溶液の和のうち最も0に近い溶液の数を出力する.

コードと結果

import sys
si = sys.stdin.readline

N = int(si())
a = sorted(list(map(int,si().split())))

ansL = 1000000000
ansR = -1000000000
sum = 2000000000
L = 0
R = N-1
while L < R:
    if a[L] + a[R] == 0:
        ansL = a[L]
        ansR = a[R]
        break
    elif a[L] + a[R] < 0:
        if abs(a[L]+a[R]) < sum:
            ansL = a[L]
            ansR = a[R]
            sum = abs(a[L]+a[R])
        L+=1
    else:
        if abs(a[L]+a[R]) < sum:
            ansL = a[L]
            ansR = a[R]
            sum = abs(a[L]+a[R])
        R-=1
    
print(ansL,ansR)