First, allocate 10,000 yen to stores of 10,000 yen or more within the range that does not exceed (10,000 yen for 10,000 yen, 10,000 yen for 10,000 yen, 20,000 yen for 20,000 yen). If you still have 10,000 yen left, allocate one by one in descending order of balance. Do the same for 5,000 yen. If there are still stores with remaining balance, Check if you can pay with a 1000 yen bill.
It was solved by repeating sorting and eliminating stores that had finished paying.
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')
Instead of repeating the sort, I could solve it using a priority queue.
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