220304-2種類の溶液

◾頭溶液:白準2470号

https://www.acmicpc.net/problem/2470

質問する
KOI建設科学研究所は多様な酸性溶液とアルカリ性溶液を持っている.各溶液には整数があり、その溶液の特性を表す.酸性溶液の特性値は、1〜10000000の正の整数で表され、塩基性溶液の特性値は−1〜10000000の負の整数で表される.
2つの溶液を等量混合した溶液の特性値は、混合に用いられる各溶液の特性値の和として定義される.この研究所は等量の2種類の溶液を混合し,特性値が最もゼロに近い溶液を作製しようとしている.
例えば、与えられた溶液の特性値が[2,4,−99,−1,98]であり、特性値が−99の溶液と特性値が98の溶液とを混合すると、特性値が−1の溶液が得られ、この溶液は特性値が最も0に近い溶液である.ちなみに、特性値が0に近い混合溶液を2種類のアルカリ溶液または2種類の酸性溶液のみで製造する場合もある.
酸性溶液とアルカリ性溶液の特性値が与えられている場合は、2つの異なる溶液を混合し、特性値が0に近い2つの溶液を見つけるプログラムを作成します.
入力

1行目に溶液全体の数Nを入力する.Nは2以上100000以下である.

2行目には、溶液特性値を示すN個の整数間のスペースが与えられる.これらの数字はいずれも-10000000以上10000000以下です.N個の溶液の特性値が異なり、酸性溶液またはアルカリ性溶液のみが入力される場合もある.

しゅつりょく

第1行出力特性値が0に近い2種類の溶液の特性値.出力が必要な2種類の溶液は特性値の昇順に出力される.プロパティ値が0の場合、2つ以上の場合、いずれかを出力します.

I/O例
InputOutput5-2 4 -99 -1 98-99 98
のり付け
1.解説

ダブルポインタでO(n)の時間的複雑さを解決できます.

溶液特性を昇順に並べ、左、右インデックスで探索する.

インデックスの値を合わせてゼロに近い値をとる.

値が負の場合は左インデックス+1、値が正の場合は右インデックス-1

合計値が0の場合はその値を返却

2.プログラム

n、入力値(昇順ソート)

左、右、result、min value初期化

左・右インデックス位置の値の和を比較する

負数左+1、正数右-1

合計値が0なら終了

# 코드
n = int(input())
values = sorted(map(int, input().split(' ')))

left = 0
right = n-1
result = [values[left], values[right]]
min_value = abs(values[left] + values[right])
while left < right:
    temp = values[left] + values[right]
    if abs(temp) < min_value:
        min_value = abs(temp)
        result = [values[left], values[right]]
    if temp < 0:
        left += 1
    elif temp > 0:
        right -= 1
    else :
        break
print(result[0], result[1])

Input
5
-2 4 -99 -1 98