Cho mảng prices, prices[i] là giá món i. Có ưu đãi: mua món i sẽ được giảm giá bằng prices[j] với j là chỉ số nhỏ nhất > i sao cho prices[j] ≤ prices[i]. Tìm mảng giá cuối cùng sau giảm giá.
Ví dụ: prices = [16,8,12,4,6] → [8,4,8,4,6].
Thuật toán
- Với mỗi i từ 0 đến len(prices)-1:
- Với j từ i+1 đến len(prices)-1:
- Nếu prices[i] ≥ prices[j]: prices[i] -= prices[j]; break.
- Trả về prices.
Ví dụ (Python)
def solve(prices):
for i in range(len(prices)):
for j in range(i+1, len(prices)):
if prices[i] >= prices[j]:
prices[i] -= prices[j]
break
return prices
prices = [16,8,12,4,6]
print(solve(prices))
Đầu vào
[16,8,12,4,6]
Đầu ra
[8, 4, 8, 4, 6]