Bulk Discount
Source: codechef
Difficulty: 1138

Bulk Discount
A shop has$N$items for sale. The$i$-th item has a cost of$A_i$.
You would like to purchase all$N$items.
The shop offers a discount: whenever an item is bought, all future purchases have their costs reduced by$1$. However, the cost of an item also cannot fall below$0$.
You can buy the items
in any order
you like. What's the minimum possible cost of purchasing all$N$items?
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains a single integer$N$— the number of items in the shop.
The second line contains$N$space-separated integers$A_1, A_2, \ldots, A_N$.
Output Format
For each test case, output on a new line the minimum possible cost of buying all$N$items.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 2\cdot 10^5$$1 \leq A_i \leq 10^9$The sum of$N$over all test cases won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
We buy the first item with a cost of$4$. This then discounts the second item by$1$, so we buy it for a cost of$2$, with the total coming out to$4+2 = 6$. This is optimal.
Test case$2$:
All the items have initial costs of$2$. The process is as follows:
Buy one item with a cost of$2$. This reduces the cost of everything else by$1$, so they're all$1$now.
Buy one item with a cost of$1$. This reduces the cost of the remaining two items by$1$again, so they both cost$0$.
Buy one item with a cost of$0$. This reduces the cost of the last item by$1$again. However, since it cannot go below$0$, it remains$0$.
Buy the last item with a cost of$0$.
The total spent is$2+1+0+0=3$.
Test case$3$:
Consider the following order:
Buy the second item, with a cost of$1$. The other items' costs will reduce by$1$.
Buy the fourth item, with a cost of$1-1 = 0$. The other items' costs will reduce by$1$.
Buy the first item, with a cost of$3-2 = 1$. The other items' costs  will reduce by$1$again.
Finally, buy the third item with a cost of$4-3 = 1$.
The total spent is$1+0+1+1 = 3$.

Sample Input:
3
2
4 3
4
2 2 2 2
4
3 1 4 1

Sample Output:
6
3
3

C++ solution:
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    
    while (T--) {
        int N;
        cin >> N;
        
        vector<int> prices(N);
        for (int i = 0; i < N; ++i) {
            cin >> prices[i];
        }
        sort(prices.begin(), prices.end());
        long long total_cost = 0;
        for(int i = 0; i < N; i++) {
            if(prices[i] <= i) continue;
            total_cost += prices[i]-i;
        }
        

        cout << total_cost << "\n";
    }

    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    tStr, _ := reader.ReadString('\n')
    T, _ := strconv.Atoi(strings.TrimSpace(tStr))

    results := make([]int, T)

    for t := 0; t < T; t++ {
        nStr, _ := reader.ReadString('\n')
        N, _ := strconv.Atoi(strings.TrimSpace(nStr))

        aStr, _ := reader.ReadString('\n')
        aSlice := strings.Fields(aStr)
        A := make([]int, N)
        for i := 0; i < N; i++ {
            A[i], _ = strconv.Atoi(aSlice[i])
        }

        sort.Ints(A)
        totalCost := 0
        for i := 0; i < N; i++ {
            if A[i] > i {
                totalCost += A[i] - i
            }
        }
        results[t] = totalCost
    }

    for _, res := range results {
        fmt.Println(res)
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef {
    public static void main (String[] args) throws java.lang.Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder result = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            String[] items = br.readLine().split(" ");
            int[] A = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = Integer.parseInt(items[i]);
            }
            Arrays.sort(A);
            long totalCost = 0;
            for (int i = 0; i < N; i++) {
                totalCost += Math.max(A[i] - i, 0);
            }
            result.append(totalCost).append("\n");
        }
        System.out.print(result.toString());
    }
}

JavaScript solution:
// your code goes here
// Read input
const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
let T = parseInt(input[0]);
let results = [];

for (let t = 1; t <= T; t++) {
    // Read the size of array N
    let N = parseInt(input[t * 2 - 1]);

    // Read the array A
    let A = input[t * 2].split(' ').map(Number);

    // Sort the array
    A.sort((a, b) => a - b);

    // Calculate the total cost
    let total_cost = 0;
    for (let i = 0; i < N; i++) {
        total_cost += Math.max(0, A[i] - i);
    }

    // Append the result
    results.push(total_cost);
}

// Print all results
console.log(results.join('\n'));

Python solution:
# cook your dish here
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    T = int(data[idx])
    idx += 1

    results = []
    for _ in range(T):
        N = int(data[idx])
        idx += 1
        A = list(map(int, data[idx:idx+N]))
        idx += N

        A.sort()
        total_cost = 0
        for i in range(N):
            total_cost += max(0, A[i] - i)
        results.append(str(total_cost))
    
    print("\n".join(results))

# Run the main function
if __name__ == "__main__":
    main()

Ruby solution:
def main
  # Read all input at once for efficiency
  input = $stdin.read.split("\n").map(&:strip).reject(&:empty?)
  idx = 0
  test_cases = input[idx].to_i
  idx += 1

  results = []
  
  test_cases.times do
    item_count = input[idx].to_i
    idx += 1
    prices = input[idx].split.map(&:to_i)
    idx += 1

    # Sort prices to maximize discounts
    prices.sort!
    
    total = 0
    prices.each_with_index do |price, i|
      # Apply discount (subtract number of items already bought)
      discounted_price = price - i
      # Price can't go below 0
      total += [discounted_price, 0].max
    end
    
    results << total.to_s
  end

  # Output all results
  puts results.join("\n")
end

main