FastPrep
Problem · Greedy

Maximize Strength of Machines

● HardFULLTIMEOA

There are n machines each equipped with m power units (m >= 2). The power of the jthunit in the i-thmachine is denoted as machine_power[i][j]. The strength of a machine is defined as the minimum power among all its power units. We want to maximize the sum of the strength of all possible machines. For this, we can perform a 3-step operation multiple times (possibly 0):

  • Select a machine that has not yet been marked.
  • Transfer any one power unit from the selected machine to any other machine.
  • Mark the selected machine, and it cannot be chosen for further operations. However, a marked machine can still receive power units from other machines.

    • Find the max sum of the strength of all machines.

    Note:

  • Each machine can transfer at most one power unit during the entire process, only when it is unmarked.
  • A machine can receive power units from multiple other machines, even after it has been marked.
  • The operation can be performed multiple times, but only unmarked machines can be selected during each operation.

    • Examples
    01 · Example 1
    n = 3
m = 2
machine_power = [[1,5],[4,3],[2,10]]
return = 16
    The operation are as follows: Select machine 1 and transfer the unit with power 1 to machine 2. now machine powers are = [[5],[1,4,3],[2,10]] Select machine 3 and transfer the unit with power 2 to machine 2 now machine powers are = [[5],[1,2,4,3],[10]] The sum of strenght is min(5) + min(1,2,4,3) + min(10) = 16 Return 16.
    drafts saved locally
    public int maximizeStrengthOfMachines(int n, int m, int[][] machine_power) {
  // write your code here
}
    n3
    m2
    machine_power[[1,5],[4,3],[2,10]]
    expected16
    checking account