АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Прианка контайнераар тоглоом хүргэдэг олон улсын компанид ажилладаг. 

 Түүний даалгавар нь хамгийн бага өртгөөр захиалгуудаа хүргэх аргыг тодорхойлох.

Түүнд бүтээгдэхүүнүүдийн жингүүд өгөгдсөн байгаа. Хүргэлтийн компаний нэг контайнерт ачсан тоглоом

тус бүрийн жин хамгийн ихдээ 4 нэгж нэмэх нь хамгийн бага жинтэй тоглоомны жин байх дүрэмтэй.

Тухайн шаардлагад нийцсэн бүх тоглоомнуудыг нэг контайнерт ачиж хүргэж болно.

Хамгийн багадаа хэдэн контайнер шаардлагатай вэ?

Жишээ нь :

дараах жингийн дараалал өгөгдөв. W = [1, 2, 3, 4, 5, 10, 11, 12, 13].

Өгөгдсөн тоглоомнуудыг 2 контайнерт хувааж ачих боломжтой. [1, 2, 3, 4, 5] ба [10, 11, 12, 13].

Контайнер тус бүрийн тоглоомнуудын хамгийн их болон бага жинтэй тоглоомнуудын хоорондын ялгаа 4 нэгж дотор.

Функцийн тайлбар

Toys функцыг бич. Хамгийн багадаа хэрэг болох контайнерын тоог хэвлэнэ үү.

Toys доорх өгөгдөлийг хүлээн авна

• W: захиалгын нийт тоглоомнуудын жинг агуулсан массив өгөгдөнө.

Оролтийн бүтэц

Эхний мөрөнд бүхэл тоо , n , захиалгат тоглоомын тоо

Дараагийн мөрөнд n ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд өгөгдөнө. W[1], W[2], …, W[n].

Хязгаарлалт

1 <= n <= 10⁵

0 <= w[i ]<= 10⁴  , 1 <= i <= n.

1<=order[i], prep[i]<=10⁶

Гаралтын бүтэц

Нэр мөрөнд бүх тоглоомыг хүргэхэд хамгийн багадаа шаардагдах контайнерын тоог хэвлэнэ үү.

Жишээ оролт

8

1 2 3 21 7 12 14 21

Жишээ гаралт

4

Тайлбар

Эхний контайнерт 1, 2, 3 жинтэй тоглоомнуудыг ачна. (жингийн хязгаар 1 … 5)

Хоёр дахь контайнерт 21 жинтэй тоглоомыг ачна. (жингийн хязгаар 21 … 25)

Гурав дахь контайнерт 7 жинтэй тоглоомнуудыг ачна. (жингийн хязгаар 7 … 11)

Дөрөв дэх контайнерт 12, 14 жинтэй тоглоомнуудыг ачна. (жингийн хязгаар 12 … 14)

Орчуулсан : Б.Мөнхбаяр АНУ