Retail Inventory Management :
Difficulty Level : Easy
Submissions : 260
Asked In :
Marks :10
: 3 | : 0
You are given an integer array $$$A$$$ containing $$$N$$$ integers. You will perform the following operation on this array until there are no more elements left in the array.
- Let $$$i$$$ be the index of the current smallest element in $$$A$$$. If there are multiple such elements, we choose $$$i$$$ to be the smallest of them. Add $$$A[i]$$$ to your score and delete $$$A[i]$$$, $$$A[i-1]$$$ and $$$A[i+1]$$$ (provided they exist).
Your task is to find the total score after you delete the entire array.
The first line of input contains an integer $$$t \hspace{2pt} (1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains an integer $$$n \hspace{2pt} (1 \le n \le 10^5)$$$ — the number of elements in the array $$$A$$$.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_0, a_1, ... a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5.$$$
For each testcase, print a single integer — the total score after deleting the entire array $$$A$$$.
244 3 2 176 4 9 10 34 56 54
4 68
In sample test case 1, you perform the following operations:
- First,choose the minimum weight (i.e., $$$1$$$) and add that weight up to the total. The products with weights $$$2$$$ and $$$1$$$ are removed. The array of products is now $$$[4,3]$$$.
- Then, choose the minimum weight from the remaining products (i.e., 3) and add that weight up to the total.The products with weights $$$3$$$ and $$$4$$$ are removed, and now there are no more products in the inventory.
Hence,the total is $$$1+3=4.$$$
In sample test case 2, you perform the following operations:
- First, select the minimum weight, $$$4$$$. Its adjacent products have weights $$$6$$$ and $$$9$$$. Weights $$$6$$$, $$$9$$$, and $$$4$$$ will be removed from products.
- The new minimum weight is $$$10$$$. So, $$$34$$$ and $$$10$$$ will be removed.
- At last,the minimum weight is $$$54$$$. So, $$$56$$$ and $$$54$$$ will be removed.
