KOI ๋ถ์ค ๊ณผํ์ฐ๊ตฌ์์์๋ ๋ง์ ์ข ๋ฅ์ ์ฐ์ฑ ์ฉ์ก๊ณผ ์์นผ๋ฆฌ์ฑ ์ฉ์ก์ ๋ณด์ ํ๊ณ ์๋ค. ๊ฐ ์ฉ์ก์๋ ๊ทธ ์ฉ์ก์ ํน์ฑ์ ๋ํ๋ด๋ ํ๋์ ์ ์๊ฐ ์ฃผ์ด์ ธ์๋ค. ์ฐ์ฑ ์ฉ์ก์ ํน์ฑ๊ฐ์ 1๋ถํฐ 1,000,000,000๊น์ง์ ์์ ์ ์๋ก ๋ํ๋ด๊ณ , ์์นผ๋ฆฌ์ฑ ์ฉ์ก์ ํน์ฑ๊ฐ์ -1๋ถํฐ -1,000,000,000๊น์ง์ ์์ ์ ์๋ก ๋ํ๋ธ๋ค.
๊ฐ์ ์์ ๋ ์ฉ์ก์ ํผํฉํ ์ฉ์ก์ ํน์ฑ๊ฐ์ ํผํฉ์ ์ฌ์ฉ๋ ๊ฐ ์ฉ์ก์ ํน์ฑ๊ฐ์ ํฉ์ผ๋ก ์ ์ํ๋ค. ์ด ์ฐ๊ตฌ์์์๋ ๊ฐ์ ์์ ๋ ์ฉ์ก์ ํผํฉํ์ฌ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค๋ ค๊ณ ํ๋ค.
์๋ฅผ ๋ค์ด, ์ฃผ์ด์ง ์ฉ์ก๋ค์ ํน์ฑ๊ฐ์ด [-2, 4, -99, -1, 98]์ธ ๊ฒฝ์ฐ์๋ ํน์ฑ๊ฐ์ด -99์ธ ์ฉ์ก๊ณผ ํน์ฑ๊ฐ์ด 98์ธ ์ฉ์ก์ ํผํฉํ๋ฉด ํน์ฑ๊ฐ์ด -1์ธ ์ฉ์ก์ ๋ง๋ค ์ ์๊ณ , ์ด ์ฉ์ก์ด ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ด๋ค. ์ฐธ๊ณ ๋ก, ๋ ์ข ๋ฅ์ ์์นผ๋ฆฌ์ฑ ์ฉ์ก๋ง์ผ๋ก๋ ํน์ ๋ ์ข ๋ฅ์ ์ฐ์ฑ ์ฉ์ก๋ง์ผ๋ก ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ํผํฉ ์ฉ์ก์ ๋ง๋๋ ๊ฒฝ์ฐ๋ ์กด์ฌํ ์ ์๋ค.
์ฐ์ฑ ์ฉ์ก๊ณผ ์์นผ๋ฆฌ์ฑ ์ฉ์ก์ ํน์ฑ๊ฐ์ด ์ฃผ์ด์ก์ ๋, ์ด ์ค ๋ ๊ฐ์ ์๋ก ๋ค๋ฅธ ์ฉ์ก์ ํผํฉํ์ฌ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค์ด๋ด๋ ๋ ์ฉ์ก์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์
๋ ฅ
์ฒซ์งธ ์ค์๋ ์ ์ฒด ์ฉ์ก์ ์ N์ด ์
๋ ฅ๋๋ค. N์ 2 ์ด์ 100,000 ์ดํ์ด๋ค. ๋์งธ ์ค์๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ๋ํ๋ด๋ N๊ฐ์ ์ ์๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. ์ด ์๋ค์ ๋ชจ๋ -1,000,000,000 ์ด์ 1,000,000,000 ์ดํ์ด๋ค. N๊ฐ์ ์ฉ์ก๋ค์ ํน์ฑ๊ฐ์ ๋ชจ๋ ๋ค๋ฅด๊ณ , ์ฐ์ฑ ์ฉ์ก๋ง์ผ๋ก๋ ์์นผ๋ฆฌ์ฑ ์ฉ์ก๋ง์ผ๋ก ์
๋ ฅ์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ๋ ์์ ์ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค์ด๋ด๋ ๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ์ถ๋ ฅํ๋ค. ์ถ๋ ฅํด์ผ ํ๋ ๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ถ๋ ฅํ๋ค. ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค์ด๋ด๋ ๊ฒฝ์ฐ๊ฐ ๋ ๊ฐ ์ด์์ผ ๊ฒฝ์ฐ์๋ ๊ทธ ์ค ์๋ฌด๊ฒ์ด๋ ํ๋๋ฅผ ์ถ๋ ฅํ๋ค.
๋ ํฌ์ธํฐ ๋ฌธ์ ๋ผ๊ณ ํ๋๋ฐ ์ฒ์ ๋ดค์ ๋ ํฌ ํฌ์ธํฐ๊ฐ ๋ญ์ง ๋ชฐ๋ผ์ ์ ํ๋ธ์ ๋์์ ์ข ๋ฐ์๋ค. https://www.youtube.com/watch?v=ttLRltNDiCo
๋์ถฉ ๋ ๊ฐ์ ์ธ๋ฑ์ค๋ฅผ ๊ฐ์ง๊ณ ์ ๋ต์ ์ ๊ทผํด๊ฐ๋ ๋ฐฉ์์ผ๋ก ํธ๋ ๊ฑฐ ๊ฐ์๋ค. ์ด๋ถํ์์ผ๋ก๋ ํ ์ ์๋ค๊ณ ํด์ ๋ ๊ฐ์ง ๋ฐฉ์์ผ๋ก ๋ค ํ์ด๋ณด๋ ํ์ด
- ์๋ก ๋ค๋ฅธ ๋ ์ฉ์ก์ ํผํฉํ๋๊ฑฐ์ง ๋ ์ฉ์ก์ด ๋ฐ๋์ ์์นผ๋ฆฌ์ฑ / ์ฐ์ฑ์ด์ฌ์ผ ํ ํ์ ์๋ค. ์ฐ์ฑ ๋ ์ฉ์ก์ ํฉ์ณ๋ 0์ ๊ฐ๊น๊ธฐ๋ง ํ๋ฉด ๋๋ค
- 0์ด ๋ ์ ์๋ ๊ฐ์ ์ฐพ๋ ๊ฒ ์๋๋ผ 0์ ๊ฐ์ฅ ๊ฐ๊น์ฐ๋ฉด ๋๋ค
- ์ฉ์ก์ด ๊ฐ์ง ์ ์๋ ์ต๋ ๊ฐ์ด 1,000,000,000์ด๋ฏ๋ก ์ต๋๊ฐ ์ค์ ์ 1e9๋ก ํ๊ฒ ๋๋ฉด ์๋ฌ๋๋ค
solution.sort()
l, r = 0, N-1
min_diff, min_sols = 1e13, []
while l < r:
tmp = solution[l] + solution[r]
if abs(tmp) < min_diff:
min_diff = abs(tmp)
min_sols = [l, r]
if tmp >= 0:
r -= 1
else:
l += 1
def sol(N, solution):
solution.sort()
min_sols, min_diff = [solution[0], solution[N-1]], 1e13
for i in range(N-1):
sol1 = solution[i]
l, r, m = i+1, N-1, 0
while l <= r:
m = (l+r)//2
tmp_sum = sol1+solution[m]
if abs(tmp_sum) < min_diff:
min_diff, min_sols = abs(tmp_sum), [sol1, solution[m]]
if tmp_sum < 0:
l = m+1
else:
r = m-1
print(*min_sols)
N = int(input())
solution = list(map(int, input().split()))
sol(N, solution)
# 92ms
def sol(N, solution):
solution.sort()
l, r = 0, N-1
min_diff, min_sols = 1e13, []
while l < r:
tmp = solution[l] + solution[r]
print(tmp)
if abs(tmp) < min_diff:
min_diff = abs(tmp)
min_sols = [l, r]
if tmp >= 0:
r -= 1
else:
l += 1
print(solution[min_sols[0]], solution[min_sols[1]])
N = int(input())
solution = list(map(int, input().split()))
sol(N, solution)
def sol(N, solution):
solution.sort()
min_sols, min_diff = [solution[0], solution[N-1]], 1e13
for i in range(N-1):
sol1 = solution[i]
l, r, m = i+1, N-1, 0
while l <= r:
m = (l+r)//2
tmp_sum = sol1+solution[m]
if abs(tmp_sum) < min_diff:
min_diff, min_sols = abs(tmp_sum), [sol1, solution[m]]
if tmp_sum < 0:
l = m+1
else:
r = m-1
print(*min_sols)
N = int(input())
solution = list(map(int, input().split()))
sol(N, solution)
3
-1 0 1
-1 1
4
-3 -1 1 10
-1 1
5
-100 -50 20 40 80
-50 40
4
-3 1 2 10
-3 2