[伯俊]2470:二種類の溶液

質問する

詰まった部分

どこで李辰探索を書くべきか分からない.
彼だ!ふふっ!知らない!!!
溶液特性値リストから2つの合計を選択し、それらを用いてバイナリ検索...?よくわかりません.

配布が必要な数量

ルータをインストールする問題は、左、右、中央の値がインデックスではなく、ルータをインストールする村間の距離です.
この問題の左、右、mid値はリストのインデックスです!
1)両溶液の特性値の和は0
whileは文を中断し、結果を出力します.
2)両溶液の特性値の和が負の場合
負の特性値は正の特性値より大きいため、left += 1により両溶液の特性値の和をゼロに近づける
3)両溶液の特性値の和は正である.
正の特性値は負の特性値のスロットル値より大きいため、right -= 1によって両溶液の特性値の和をゼロに近づける

最小インデックス値を求める左、右インデックス値の更新部分

特性値が0に最も近い溶液を生成しなければならないので、スロットル値は小さくなければならない.
2つの溶液の特性値の合計が既存の解答の節気値より小さい場合は、解答に新しい値を入力します.
+)
左と右のインデックス値をそれぞれ2つの変数に格納
(スロットル値:-2,1を使用すると、スロットル値-2を使用せずにminに出力されるので、スロットル値を使用する必要があります)
https://data-bank.tistory.com/29

こうぞう

リストに溶液の特性値を入力します.

リストを昇順に並べます.

これを

左=0、右=N-1に設定し、while文を左<右に繰り返し、ユーザーにナビゲートします.
(原因:両方の溶液が異なる)

i)両溶液の特性値の和は0である.

whileは文を中断し、結果を出力します.

ii)両溶液の特性値の和が負の場合

の負の特性値の節気値は正の特性値の節気値より大きいため、left+=1は2つの溶液の特性値の和をゼロに近づけることができる.

iii)両溶液の特性値の和が正の場合

正の特性値の断面積値は負の特性値の断面積値より大きいため、right−=1は2つの溶液の特性値の和がゼロに近いことを許容する.

2つの溶液の特性値の和が既存の答えの和より小さい場合、答えに新しい値を入力し、al=left、ar=rightでindexを保存します.minを使用すると、-2と1を比較するときに、答えに-2が入力されます.これは誤った答えなので、節制値を使用できます.

ソース
https://data-bank.tistory.com/29

再試行22.04.12

import sys

N = int(sys.stdin.readline())
W = sorted(list(map(int, sys.stdin.readline().split()))) # 오름차순으로 정렬

start = 0
end = N - 1
minValue = W[0] + W[N-1]
x = start
y = end

while start < end:
    sum = W[start] + W[end]
    
    if sum == 0:
        x = start
        y = end
        break
    
    if abs(minValue) > abs(sum):
        x = start
        y = end
        minValue = sum
   
    if sum > 0:
        end -= 1
    elif sum < 0:
        start += 1
    
print(W[x], W[y])

他人を解く

import sys

n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))

w.sort()
left = 0
right = n - 1
answer = w[left] + w[right] # 처음에는 가장 작은 수와 가장 큰 수를 더한 합을 answer로 넣어둠
al = left
ar = right

while left < right:
    tmp = w[left] + w[right] # "현재 left와 right의 합"인 tmp와 기존의 최솟값인 answer를 비교해서 최솟값을 계속 갱신해주는 것
    if abs(tmp) < abs(answer): # 기존 answer보다 "현재 left와 right의 합"인 tmp 가 작을 때 최솟값을 갱신
        answer = tmp # 현재 합인 tmp를 answer에 넣어줌
        al = left
        ar = right
        if answer == 0: # 만약 합이 0이 되면 break 해줌
            break
    
    if tmp < 0:
        left += 1 # 합이 음수이면 음수의 절댓값이 양수의 절댓값보다 큰 것이기 때문에 left += 1
    else:
        right -= 1 # 합이 양수이면 양수의 절댓값이 음수의 절댓값보다 큰 것이기 때문에 right -= 1
    
print(w[al], w[ar])
        

私の草!

この探索はleft < rightでしかできません!!left = rightの箱を含めることができないのは、溶液が異なるためです.
最初はleft <= rightずっと96%でエラー!現れる
他の人の解答を見て分かるように、私はアルカリ性と酸性がいくつもある場合にのみ二分探索を行い、すべてのケースを二分探索する必要がなければ火をつける.
ソートがよければ必ずこちらを検索します!

import sys
n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))
w = sorted(w)
a = [] # 알칼리성 음의 정수
s = [] # 산성 양의 정수

al = 0 # left 인덱스
ar = 0 # right 인덱스

# 알칼리성과 산성을 분류
for i in w:
    if i < 0:
        a.append(i)
    elif i > 0:
        s.append(i)
a = sorted(a)
s = sorted(s)

if len(s) == 0 and len(a) > 0: # 음수인 것만 있을 때
    print(a[-2], a[-1])
elif len(a) == 0 and len(s) > 0: # 양수인 것만 있을 때
    print(s[0], s[1])
else: # 음수와 양수의 조합
    # 음수가 한 개이고 양수가 여러개
    if len(a) == 1 and len(s) > 1:
        al = 0
        ar = 1
        p = 0
        tmp = s[0] + s[1] # 양수인 것 두 개의 합
        for i in range(len(s)):
            if tmp > abs(a[0] + s[i]): # 음수 한 개와 양수 여러개들의 합이 양수 작은 것 두개의 합보다 작으면 업데이트
                tmp = abs(a[0] + s[i])
                al = 0
                ar = i
                p = 1
        # 프린트
        if p == 1:
            print(a[0], s[ar])
        elif p == 0:
            print(s[0], s[1])
        
    # 양수가 한 개이고 음수가 여러개
    elif len(s) == 1 and len(a) > 1:
        al = -2
        ar = -1
        p = 0
        tmp = abs(a[-2] + a[-1]) # 음수인 것 두 개의 합
        for i in range(len(a)):
            if tmp > abs(s[0] + a[i]): # 양수 한 개와 음수 여러개들의 합이 음수 작은 것 두개의 절댓값의 합보다 작으면 업데이트
                tmp = abs(s[0] + a[i])
                al = 0
                ar = i
                p = 1
        # 프린트
        if p == 1:
            print(a[ar], s[0])
        elif p == 0:
            print(a[-2], a[-1])
    
    elif len(s) == 1 and len(a) == 1:
        print(a[0], s[0])
    
    # 둘 다 여러 개
    else:
        left = 0
        right = len(w) - 1
        
        al = 0
        ar = 0
        tmp = float('inf')
        
        while left < right: # 용액은 모두 서로 다르기 때문에 left = right으로 인덱스가 같은 케이스는 포함시켜주면 안 됨!
            if tmp > abs(w[left] + w[right]):
                al = left
                ar = right
                tmp = abs(w[left] + w[right])
            
            if w[left] + w[right] == 0:
                al = left
                ar = right
                break
            elif w[left] + w[right] < 0:
                left += 1
            
            else:
                right -= 1
            
        print(w[al], w[ar])