Tout d'abord, allouez 10 000 yens aux magasins de 10 000 yens ou plus dans la fourchette qui ne dépasse pas (10 000 yens pour 10 000 yens, 10 000 yens pour 10 000 yens, 20 000 yens pour 20 000 yens). S'il vous reste 10 000 yens après l'affectation, répartissez-les un par un dans l'ordre décroissant du solde. Faites de même pour 5 000 yens. S'il y a encore des magasins avec un solde restant, Vérifiez si vous pouvez payer avec une facture de mille yens.
Il a été résolu en répétant le tri et en excluant les magasins qui avaient été payés.
N, X, Y, Z = map(int, input().split())
A = list(map(int, input().split()))
A = [a + 1 for a in A]
A.sort(reverse=True)
for i in range(len(A)):
if Z == 0:
break
if A[i] >= 10000:
t = A[i] // 10000
t = min(t, Z)
Z -= t
A[i] -= t * 10000
else:
break
A = [a for a in A if a > 0]
A.sort(reverse=True)
A = A[Z:]
for i in range(len(A)):
if Y == 0:
break
if A[i] >= 5000:
t = A[i] // 5000
t = min(t, Y)
Y -= t
A[i] -= t * 5000
else:
break
A = [a for a in A if a > 0]
A.sort(reverse=True)
A = A[Y:]
for i in range(len(A)):
t = (A[i] + 999) // 1000
t = min(t, X)
X -= t
A[i] -= t * 1000
A = [a for a in A if a > 0]
if len(A) == 0:
print('Yes')
else:
print('No')
Au lieu de répéter le tri, je pourrais le résoudre en utilisant une file d'attente prioritaire.
from heapq import heapify, heappop, heappush
N, X, Y, Z = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapify(A)
while A:
if Z == 0:
break
x = -heappop(A)
if x >= 10000:
t = min(x // 10000, Z)
Z -= t
x -= 10000 * t
heappush(A, -x)
else:
Z -= 1
while A:
if Y == 0:
break
x = -heappop(A)
if x >= 5000:
t = min(x // 5000, Y)
Y -= t
x -= 5000 * t
heappush(A, -x)
else:
Y -= 1
while A:
if X == 0:
break
x = -heappop(A)
t = min((x + 1000) // 1000, X)
X -= t
x -= t * 1000
if x >= 0:
heappush(A, -x)
if len(A) == 0:
print('Yes')
else:
print('No')
Recommended Posts