Chương trình tìm ra số lượng hộp được đưa vào Godown bằng Python

Giả sử, chúng ta có hai mảng chứa các số nguyên. Một danh sách chứa chiều cao của một số hộp có chiều rộng đơn vị và một mảng khác chứa chiều cao của các phòng trong trang phục. Các phòng được đánh số 0 ... n và chiều cao của các phòng được cung cấp trong các chỉ mục tương ứng của chúng trong phần bổ trợ của mảng. Chúng ta phải tìm ra số lượng hộp có thể được đẩy vào Godown. một số điều cần phải ghi nhớ,

• Không thể đặt các hộp này lên nhau.

• Thứ tự của các hộp có thể được thay đổi.

• Các hộp chỉ được đưa vào khung đỡ từ trái sang phải.

Nếu một hộp cao hơn chiều cao của căn phòng, thì hộp cùng với tất cả các hộp ở bên phải của nó sẽ không thể được đẩy vào giàn phơi.

Vì vậy, nếu đầu vào giống như các hộp =[4,5,6], godown =[4, 5, 6, 7], thì đầu ra sẽ là 1 Chỉ có thể chèn một hộp. Phòng đầu tiên có kích thước 4 và phần còn lại không thể đẩy vào tủ thờ vì các hộp phải được đẩy qua phòng đầu tiên và chiều dài của nó nhỏ hơn các hộp khác.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp các hộp danh sách

• curmin:=một danh sách mới chứa phần tử đầu tiên của godown

• cm:=curmin [0]

• đối với tôi trong phạm vi từ 1 đến kích thước của Godown, hãy làm

  • cur:=godown [i]

  • nếu cur

    • cm:=cur

  • chèn cm vào cuối curmin

• i:=0

• j:=size of godown -1

• r:=0

• while j> =0 and i

  • nếu curmin [j]> =box [i], thì

    • i:=i + 1

    • r:=r + 1

  • j:=j - 1

• trả lại r

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(boxes, godown):
   boxes.sort()
   curmin = [godown[0]]
   cm = curmin[0]
   for i in range(1, len(godown)):
      cur = godown[i]
      if cur < cm:
         cm = cur
      curmin.append(cm)
   i,j = 0, len(godown)-1
   r = 0
   while j >= 0 and i < len(boxes):
      if curmin[j] >= boxes[i]:
         i += 1
         r += 1
      j -= 1
   return r

print(solve([4,5,6], [4, 5, 6, 7]))

Đầu vào

[4,5,6], [4, 5, 6, 7]

Đầu ra

1