Trouvez la valeur Kth dans l'ordre croissant ⇒ Trouvez le minimum x tel qu'il y ait K ou plus de x ou moins.
Le contenu est cité ci-dessous. Ce message est une note privée. ABC155 [Examen du problème D] Après avoir examiné la vidéo de commentaire avec l'élan de la transcription, le sentiment de faiblesse dans la recherche de bissection a diminué
AtCoder Beginner Contest 155 (ABC155) Commentaire A à E
Exemple de code
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
#Nombre négatif(nc), Nombre de 0(zc), Nombre positif(pc)Compter
for i in range(n):
if arr[i]<0:
nc+=1
elif arr[i]==0:
zc+=1
else:
pc+=1
#Trouvez le nombre de paires avec un produit négatif
ncc=nc*pc
#Trouvez le nombre de paires dont le produit est 0
zcc=zc*(nc+pc)+(zc*(zc-1))//2
#Trouvez le nombre de paires dont le produit est positif
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
#Si la valeur Kth est négative
if k <= ncc:
arr1=[]
arr2=[]
#Organisez les nombres négatifs et positifs dans l'ordre croissant
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 #le droit est aussi la réponse
#Puisque le calcul est effectué en prenant le moins d'un nombre négatif, la magnitude du produit est inversée, donc le Kth du plus grand
#Du plus petit(Nombre de paires avec un produit négatif-K)Trouvez la deuxième valeur
k = ncc-k
while r-l != 1: #Répétez jusqu'à ce que r et l soient une différence, c'est-à-dire que r est la réponse
mid=(l+r)//2 #Mettre à jour la valeur intermédiaire de l'intervalle
cnt=0
pos=c2-1
#section[left, right)Comment se débarrasser de
#Pour chaque nombre négatif, trouvez et ajoutez le nombre de nombres positifs dont le produit est inférieur à la valeur arbitrairement déterminée mid.
for i in range(c1):
while pos!=-1:
if arr2[pos] > mid//arr1[i]:
pos-=1
else:
break
cnt+=pos+1
#Le nombre de pièces inférieur ou égal à la valeur arbitrairement déterminée mi(Nombre de paires avec un produit négatif-K)S'il y en a plusieurs, la vraie valeur est inférieure ou égale à mi
if cnt > k:
r = mid #Mettre à jour jusqu'au milieu et recommencer
#Sinon, la valeur vraie est supérieure ou égale à mid
else:
l = mid #Mettre à jour de gauche à mi et recommencer à compter
#Puisqu'il a été calculé en prenant un nombre négatif moins, la sortie avec un moins à la fin
print(-r)
#Lorsque la valeur Kth est 0
elif k <= (ncc+zcc):
print(0)
#Si la valeur Kth est positive
else:
arr1=[]
arr2=[]
for i in range(n): #Organisez les nombres négatifs et positifs dans l'ordre croissant
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) #Je veux vérifier le nombre K dans l'ordre croissant parmi les nombres positifs, supprimez donc les nombres négatifs et les nombres 0.
while r-l != 1:
mid=(l+r)//2
cnt1=0
pos1=c1-1
#Pour chaque nombre négatif, trouvez et ajoutez le nombre de nombres négatifs dont le produit est inférieur à la valeur arbitrairement déterminée mid.(Méthode Shakutori)
for i in range(c1):
tmp=0
while pos1 != -1:
if arr1[pos1] > mid//arr1[i]:
pos1-=1
else:
break
tmp+=pos1+1
#Pour chaque élément, si le produit lors de sa sélection deux fois est inférieur ou égal à la valeur arbitrairement déterminée mid, réduisez le nombre de paires qui satisfont la condition de 1.
if arr1[i]**2 < mid:
tmp-=1
cnt1+=tmp
cnt1 = cnt1//2 #Dans le processus ci-dessus, la même paire est comptée deux fois, donc divisez par deux le nombre.
cnt2=0
pos2=c2-1
#Pour chaque nombre positif, trouvez et ajoutez le nombre de nombres positifs dont le produit est inférieur à la valeur arbitrairement déterminée mid.(Méthode Shakutori)
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 #Pour chaque élément, si le produit lors de sa sélection deux fois est inférieur ou égal à la valeur arbitrairement déterminée mid, réduisez le nombre de paires qui satisfont la condition de 1.
cnt2+=tmp
cnt2=cnt2//2 #Dans le processus ci-dessus, la même paire est comptée deux fois, donc divisez par deux le nombre.
cnt=cnt1+cnt2
if cnt >= k: #Si le nombre de pièces inférieur ou égal à la valeur arbitrairement déterminée mid est K ou plus, la vraie valeur est inférieure ou égale à mid
r = mid
else: #Sinon, la valeur vraie est supérieure ou égale à mid
l = mid
print(r)
Recommended Posts