TIL)2470両溶液

22010 ワード

この文章は、
1.未来の私がこの问题を解决したい时、过去の私はどのように问题を解决したかをあなたに教えるためです.
2.同じ問題を解決する人にアイデアを提供するため
作成されました.

👽 二種類の溶液


白準2470の2種類の溶液:https://www.acmicpc.net/problem/2470
データのサイズを見てバイナリ検索でアクセスしました.
(-10000000または10000000以下)
しかし、これ以上問題を解くなら、二重ポインタで近づけるのがもっと簡単な方法だと思います.

👩‍🏫 タイムアウト

def recur(array, start, end, num1):
    global answer
    # 종료 조건
    if start >= end:
        answer.append([num1, array[end]])
        # print("여기는 start > end : "+str(num1)+ " "+str(array[end]))
        return
    mid = (start + end)//2
    if array[mid] + num1 == 0:
        # print(f'여기는 총합이 0 : {num1} {array[mid]}')
        answer.append([num1, array[mid]])

    if array[mid] + num1 < 0:
        recur(array, mid+1, end, num1)
    elif array[mid] + num1 > 0:
        recur(array, start, mid-1, num1)



# main함수
N = int(input())
array = list(map(int, input().split()))
array.sort()
answer = []
result = []

# 음수만 있는 경우
if array[-1] <= 0:
    result = [array[-1], array[-2]]
    # print(f'{array[-1]} {array[-2]}')

# 양수만 있는 경우
elif array[0] >= 0:
    result = [array[0], array[1]]
else:
    for num1 in array:
        array.remove(num1)
        recur(array, 0, N-2, num1)
# print(answer)


abs_num = 2e9
for i in range(len(answer)):
    temp = abs(answer[i][0] + answer[i][1])
    if abs(temp) < abs_num:
        abs_num = temp
        result = [answer[i][0], answer[i][1]]
print(result)
どの部分でタイムアウトが発生したのか正確にはわかりません😥
まず、溶液が負の数であれば、譲受人をスクリーニングする.
ブレンドの場合にのみrecur()関数を呼び出し、num 1に加算すると0に最も近い数を答えに入れます.(比較でタイムアウトは発生しますか?)
こうやって解くと、答えは出てきますが、タイムアウトが発生します.

👪 隊員たちと一緒に問題を解きます。

import sys
# sys.stdin = open("./백준 문제 파일/week02/baekjoon/two-sol.txt", "r")

sol_num = int(input())
solutions = sorted(map(int, input().split()))

def find_value(solution, origin, target):
  pl = 0
  pr = len(solution)-1
  while True:
    pc = (pl + pr) // 2
    if solution[pc] == target:
      return [origin, solution[pc]]
    elif target < solution[pc]:
      pr = pc -1
    else:
      pl = pc + 1
    if pr < pl:
      if pr >= 0 and pl < len(solution):
        if solution[pl] - target <  target - solution[pr]:
          return [origin, solution[pl]]
        else:
          return [origin, solution[pr]]
      elif pr < 0:
        return [origin, solution[pl]]
      else:
        return [origin, solution[pr]]

temp_list = list()
if solutions[0] >= 0:
  print(f"{solutions[0]} {solutions[1]}")
elif solutions[-1] <= 0:
  print(f"{solutions[-2]} {solutions[-1]}")
else:
    for solution in solutions:
        temp_list.append(find_value(solutions, solution, -solution))

    new_temp_list = []
    for temp in temp_list:
        if temp[0] - temp[1] != 0:
            new_temp_list.append([abs(sum(temp)), temp])
	
    # 짝꿍 숫자의 순서가 뒤집혀 있을 경우 정렬해주기
    finally_want = sorted(new_temp_list)[0]
    # print(finally_want)
    if finally_want[1][0] > finally_want[1][1]:
        finally_want[1][0], finally_want[1][1] = finally_want[1][1], finally_want[1][0]

    print(*finally_want[1])
チームメンバーと一緒に解く場合は、find value()関数でtargetという値を求めてから入れます.そして元の数字とtargetで求めた数字をリストにまとめて返します.
タイムアウトが続いたが,反例は繰り返しを認め,4時間以内に通過した.最後まで諦めなかった選手たちは素晴らしいです.👍👍👍