Bhallaladeva was an evil king who ruled the kingdom of Maahishmati. He wanted to erect a 100ft golden statue of himself and he looted gold from several places for this. He even looted his own people, by using the following unfair strategy:
There are N houses in Maahishmati, and the ith house has Ai gold plates. Each gold plate costs exactly 1 Nimbda, which is the unit of currency in the kingdom of Maahishmati. Bhallaladeva would choose an integer K, and loots all the houses in several steps. In each step:
- He would choose a house i which hasn't been looted yet, pay the owner exactly Ai Nimbdas, and take away all the gold plates in that house (Hence, he also ends up looting this house).
- He would now choose atmost K houses which haven't been looted yet and take away all the gold plates from these houses without paying a single Nimbda (Yes, he takes all of them for free).
He repeats the above steps until all the N houses have been looted. Your task is to devise a strategy for Bhallaladeva to loot the houses in some order, so that the number of nimbdas he has to pay is minimium. You'll also be given multiple values of K (Q of them to be precise), and you need to find the minimum number of nimbdas for each of these values.
Example:
Input: 4
3 2 1 4
2
0
2
Output: 10 3
Approach
Java
import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Maahismathi {public static void main(String[] args) throws Exception {int n = 4;int[] golds = { 3, 2, 1, 4 };Arrays.sort(golds);int q = 2;int[] queries = { 0, 2 };for (int query : queries) {System.out.println(getValue(query, golds));}}static Map<Integer, Integer> memo = new HashMap<>();private static int getValue(int query, int[] golds) {if (memo.containsKey(query))return memo.get(query);int len = golds.length, paidIdx = 0, paidAmt = 0;int processed = 0;while (processed < len) {paidAmt += golds[paidIdx++];processed++;processed += query;}memo.put(query, paidAmt);return paidAmt;}}
No comments:
Post a Comment