The tower defense

Let's say you are playing a tower defense with multiple lanes. This is going to be a simple tower defense with 3 lanes. Each lane sends out a baddie with a certain amount of health every second. In each lane you must put one tower. The baddies will be something like as follows:

Lane 1 - 250 health

Lane 2 - 150 health

Lane 3 - 50 health

You have several choices for towers. 3 of them deal a certain amount of dps, but can hit any lane. I will call these pool towers since they pool their damage. The 4th tower deals an infinite amount of dps, enough to kill any baddie, but can only deal damage in its lane. Let's say the towers are as follows:

Lava - infinite dps, 70 gold/second - its lane only 

Lightning - 400 dps, 155 gold/second - pool tower

Ordnance - 90 dps, 65 gold/second - pool tower

Plasma - 45 dps, 45 gold/second - pool tower

Conduit - 0 dps, 20 gold/second - pool tower

Now, the point of this tower defense is not just to survive, which would be easy, but to do so in the most cost efficient way possible, so while you might want to put down an infinite dps tower in every lane it probably isn't your best choice.

This is a simple problem and you probably already solved it. But, what if there was a million lanes? What if there was a restriction on the conduit towers so that you can only use one of them per lightning or plasma tower? What if there was even more towers that act like the lightning tower but with different prices and dps?

Here is the way that I solved this in O(nlog(n)) time. First you need to create a list of baddies sorted by health with lowest health first. This is the log(n) of the nlog(n). If the list is already given to your sorted, all the better.

Now place Lava towers on every lane and record the total cost somewhere and call it the cheapest known cost.

What we are going to do next is work our way down the lane list, replacing one lava tower at a time with a pool tower and keeping a running total of bad guy health and the total dps of the pool towers. If you can replace the lava tower with the cheapest available tower without the total bad guy health exceeding the pool dps then pick that, and if not then pick the most cost efficient pool tower.

In this simple example, this gives you the choice of either the conduit or the lightning towers. In a more complex game, the conduit tower might not be available due to restrictions and the cheapest possible tower to place might be a plasma.

After each tower replacement check the new total cost against the cheapest known cost. If it is cheaper then record the new cheapest known cost and keep moving down the list.

Eventually you will reach a point where adding a new lightning tower may not deal enough damage to maintain tower damage above the total baddie health. You are now done with trying to replace lava towers. Take the final cheapest known tower configuration, total damage, and total baddie health in lanes with pool towers and move on. In the simple example above you would end up with 2 conduits and a lightning for your towers, 400 damage, and 400 baddie health.

Your next step is to determine whether you can trade a lightning tower for an ordnance or maybe a plasma tower while still being able to kill all the baddies. If you can, then do so. In the example above this is not possible.

The final step is only needed if there was a restriction on the conduit towers and you might end up in a situation where you can replace two plasma towers for an ordnance and a conduit. If so then do that.

Congratulations, you now have the cheapest possible tower configuration.