Cable Merchant oт Algorithms Exam - 15 May 2016
Това е условието =>
You're a merchant of the "Jicata" cable. You are given different lengths of "Jicata" {1, 2, 3, …, n} each with a different price. For example, we are given the sequence K = { 3, 8, 13, 15, 18, 20, 22 }:
Length 1 2 3 4 5 6 7
Price 3 8 13 15 18 20 22
Instead of selling a 5m cable for 18$, you noticed you can cut that cable into parts of lengths 2m (8$) and 3m (13$). Then you could use 2 connectors (to connect the cables) for a price of 2 * 1$ = 2$ and make a profit of 8 + 13 – 2 * 1 = 19$. Sneaky little bastard, aren't you?
Успях да скалъпя някакво решение , обаче въпроса ми е може ли да се оптимизира по някакъв начин http://pastebin.com/aiY9J34Q
Да , явно от стриймовете и скенера почти всеки commit беше на кантар ,а сега около 0.05s, което е доста голяма разлика.
Има ли алтернативно решение с Map или подобно , но май всъщност винаги трябва да се провери дали при ситуация да речем дължина 5 дали 4+1 или 2+3 дава по-доброто решение за момента тъй като се променят стойностите динамично.
Няма нужда от екстра колекции, понеже пътя на алгоритъма позволява да модифицираш текущата. Да - трябва да обходиш всички възможни разрязвания до i/2, както един колега на изпита разбра че дори и да пресметнеш най-добрата цена на метър за всяка вече премината дължина, понякога най-доброто решение е да не я вземеш.