Finden Sie den K-ten Wert in aufsteigender Reihenfolge ⇒ Finden Sie das Minimum x so, dass es K oder mehr von x oder weniger gibt.
Der Inhalt ist unten zitiert. Dieser Beitrag ist eine private Notiz. ABC155 [Überprüfung des D-Problems] Nach Durchsicht des Kommentarvideos mit dem Moment des Transkribierens hat das Gefühl der Schwäche bei der Halbierungssuche abgenommen
AtCoder Beginner Contest 155 (ABC155) Kommentar von A bis E
Beispielcode
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
#Negative Zahl(nc), Anzahl 0(zc), Positive Zahl(pc)Anzahl
for i in range(n):
if arr[i]<0:
nc+=1
elif arr[i]==0:
zc+=1
else:
pc+=1
#Finden Sie die Anzahl der Paare mit einem negativen Produkt
ncc=nc*pc
#Finden Sie die Anzahl der Paare, deren Produkt 0 ist
zcc=zc*(nc+pc)+(zc*(zc-1))//2
#Finden Sie die Anzahl der Paare, deren Produkt positiv ist
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
#Wenn der K-te Wert negativ ist
if k <= ncc:
arr1=[]
arr2=[]
#Ordnen Sie negative und positive Zahlen in aufsteigender Reihenfolge an
for i in range(n):
if arr[i] < 0:
arr1.append(-arr[i])
elif arr[i] > 0:
arr2.append(arr[i])
arr1=arr1[::-1]
c1=len(arr1)
c2=len(arr2)
l = 0 # left
r = 10**18+1 #Richtig ist auch die Antwort
#Da die Berechnung unter Verwendung des Minus einer negativen Zahl durchgeführt wird, wird die Größe des Produkts umgekehrt, so dass der K-te vom größten ist
#Vom kleinsten(Anzahl der Paare mit einem negativen Produkt-K)Finden Sie den zweiten Wert
k = ncc-k
while r-l != 1: #Wiederholen, bis r und l ein Unterschied sind, dh r ist die Antwort
mid=(l+r)//2 #Aktualisieren Sie den Zwischenwert des Intervalls
cnt=0
pos=c2-1
#Sektion[left, right)Wie man loswird
#Suchen und addieren Sie für jede negative Zahl die Anzahl der positiven Zahlen, deren Produkt kleiner als der willkürlich bestimmte Wert mid ist.
for i in range(c1):
while pos!=-1:
if arr2[pos] > mid//arr1[i]:
pos-=1
else:
break
cnt+=pos+1
#Die Anzahl der Teile, die kleiner oder gleich dem willkürlich bestimmten Wert mid sind(Anzahl der Paare mit einem negativen Produkt-K)Wenn mehr als eins vorhanden ist, ist der wahre Wert kleiner oder gleich der Mitte
if cnt > k:
r = mid #Aktualisieren Sie von rechts auf Mitte und beginnen Sie von vorne
#Andernfalls ist der wahre Wert größer oder gleich mid
else:
l = mid #Aktualisieren Sie von links auf Mitte und beginnen Sie erneut zu zählen
#Da es mit einer negativen Minuszahl berechnet wurde, wird am Ende ein Minus ausgegeben
print(-r)
#Wenn der K-te Wert 0 ist
elif k <= (ncc+zcc):
print(0)
#Wenn der K-te Wert positiv ist
else:
arr1=[]
arr2=[]
for i in range(n): #Ordnen Sie negative und positive Zahlen in aufsteigender Reihenfolge an
if arr[i] < 0:
arr1.append(-arr[i])
elif arr[i] > 0:
arr2.append(arr[i])
arr1=arr1[::-1]
c1=len(arr1)
c2=len(arr2)
l=0
r=10**18+1
k -= (ncc+zcc) #Ich möchte die K-te Zahl in aufsteigender Reihenfolge unter den positiven Zahlen überprüfen, also negative Zahlen und 0-Zahlen entfernen.
while r-l != 1:
mid=(l+r)//2
cnt1=0
pos1=c1-1
#Suchen und addieren Sie für jede negative Zahl die Anzahl der negativen Zahlen, deren Produkt kleiner als der willkürlich bestimmte Wert mid ist.(Shakutori-Methode)
for i in range(c1):
tmp=0
while pos1 != -1:
if arr1[pos1] > mid//arr1[i]:
pos1-=1
else:
break
tmp+=pos1+1
#Wenn für jedes Element das Produkt der zweimaligen Auswahl kleiner oder gleich dem willkürlich bestimmten Wert mid ist, wird die Anzahl der Paare, die die Bedingung erfüllen, um 1 verringert.
if arr1[i]**2 < mid:
tmp-=1
cnt1+=tmp
cnt1 = cnt1//2 #Bei dem obigen Vorgang wird dasselbe Paar zweimal gezählt, also halbieren Sie die Zahl.
cnt2=0
pos2=c2-1
#Suchen und addieren Sie für jede positive Zahl die Anzahl der positiven Zahlen, deren Produkt kleiner als der willkürlich bestimmte Wert mid ist.(Shakutori-Methode)
for i in range(c2):
tmp=0
while pos2!=-1:
if arr2[pos2] > mid//arr2[i]:
pos2-=1
else:
break
tmp+=pos2+1
if arr2[i]**2 < mid:
tmp-=1 #Wenn für jedes Element das Produkt der zweimaligen Auswahl kleiner oder gleich dem willkürlich bestimmten Wert mid ist, wird die Anzahl der Paare, die die Bedingung erfüllen, um 1 verringert.
cnt2+=tmp
cnt2=cnt2//2 #Bei dem obigen Vorgang wird dasselbe Paar zweimal gezählt, also halbieren Sie die Zahl.
cnt=cnt1+cnt2
if cnt >= k: #Wenn die Anzahl der Teile, die kleiner oder gleich dem willkürlich bestimmten Wert mid sind, K oder mehr ist, ist der wahre Wert kleiner oder gleich mid
r = mid
else: #Andernfalls ist der wahre Wert größer oder gleich mid
l = mid
print(r)
Recommended Posts