Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Greedy algorithm, Priority Queues
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
Himanshu now wants to become the king. He has
N persons to defeat before he can become the King. He can choose any two persons and can fight with them, the strength needed for this is equal to the sum of both the persons. But whenever two persons are defeated they get killed and a new person borns with the combined strength of two person defeated. The fight continues until there is only one person left.Help Himanshu find the minimum strength he should waste to become king.
See original problem statement here
For Example :
1
3
2 3 4
14
Himanshu defeats 2 ,3
so the list of opponents becomes 5 ,4
then Himanshu defeats them.
So the strength required is (2+3)+(5+4)=14.
OBSERVATION:
Since the new person born has the combined strength of two defeated persons, To minimize the strength of the new person and hence the total strength of king ,We must choose the two persons with the least strength at each iteration.
For example, in the given test case, if Himanshu chooses the person with strength 2 and the person with strength 4 first ,the list becomes – 6,3 .
Then after defeating them , the overall strength required becomes: 6+9=15 ,which is greater than what we got by selecting the least everytime.
SOLVING APPROACH:
In order to minimize the sum, the people who get chosen at every step must be the ones with minimum strength from the list. In order to do that efficiently, a priority queue can be used.
At each iteration, select the ones with minimum and second minimum strength .
Add the two and push back the sum to the list.
Also,keep updating the total sum!
SOLUTIONS:
#include <stdio.h>
#include <stdlib.h>
struct MinHeap {
unsigned size;
unsigned capacity;
int* harr;
};
struct MinHeap* createMinHeap(unsigned capacity)
{
//struct MinHeap* minHeap = new MinHeap;
struct MinHeap* minHeap;
int n=1;
minHeap = (struct MinHeap*)malloc(n * sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->harr = (int*)malloc(capacity * sizeof(int));
return minHeap;
}
void swapMinHeapNode(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->harr[left] < minHeap->harr[smallest])
smallest = left;
if (right < minHeap->size && minHeap->harr[right] < minHeap->harr[smallest])
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->harr[smallest], &minHeap->harr[idx]);
minHeapify(minHeap, smallest);
}
}
int isSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
int extractMin(struct MinHeap* minHeap)
{
int temp = minHeap->harr[0];
minHeap->harr[0] = minHeap->harr[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(struct MinHeap* minHeap, int val)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && (val < minHeap->harr[(i - 1) / 2])) {
minHeap->harr[i] = minHeap->harr[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->harr[i] = val;
}
void buildMinHeap(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
struct MinHeap* createAndBuildMinHeap(int len[], int size)
{
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->harr[i] = len[i];
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
int minCost(int len[], int n)
{
int cost = 0;
struct MinHeap* minHeap = createAndBuildMinHeap(len, n);
while (!isSizeOne(minHeap)) {
int min = extractMin(minHeap);
int sec_min = extractMin(minHeap);
cost += (min + sec_min);
insertMinHeap(minHeap, min + sec_min);
}
return cost;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("%d\n",minCost(arr,n));
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct MinHeap {
unsigned size;
unsigned capacity;
int* harr;
};
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap = new MinHeap;
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->harr = new int[capacity];
return minHeap;
}
void swapMinHeapNode(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->harr[left] < minHeap->harr[smallest])
smallest = left;
if (right < minHeap->size && minHeap->harr[right] < minHeap->harr[smallest])
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->harr[smallest], &minHeap->harr[idx]);
minHeapify(minHeap, smallest);
}
}
int isSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
int extractMin(struct MinHeap* minHeap)
{
int temp = minHeap->harr[0];
minHeap->harr[0] = minHeap->harr[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(struct MinHeap* minHeap, int val)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && (val < minHeap->harr[(i - 1) / 2])) {
minHeap->harr[i] = minHeap->harr[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->harr[i] = val;
}
void buildMinHeap(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
struct MinHeap* createAndBuildMinHeap(int len[], int size)
{
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->harr[i] = len[i];
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
int minCost(int len[], int n)
{
int cost = 0;
struct MinHeap* minHeap = createAndBuildMinHeap(len, n);
while (!isSizeOne(minHeap)) {
int min = extractMin(minHeap);
int sec_min = extractMin(minHeap);
cost += (min + sec_min);
insertMinHeap(minHeap, min + sec_min);
}
return cost;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<minCost(arr,n)<<endl;;
}
return 0;
}
import java.util.*;
import java.util.PriorityQueue;
class King
{
static int MinSum(int arr[], int n)
{
int i, sum = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (i = 0; i < n; i++)
pq.add(arr[i]);
while (pq.size() > 1)
{
int min = pq.poll();
int secondMin = pq.poll();
sum += (min + secondMin);
pq.add(min + secondMin);
}
return sum;
}
public static void main(String[] args)
{ Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
System.out.println(MinSum(arr, n)); }
}
}
[forminator_quiz id="1434"]
This article tried to discuss Greedy algorithm, Priority Queues. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm, Priority Queues you can check out MYCODE | Competitive Programming.