Ok I will prove it, so my memory doesn’t betray me.
Consider some set of n-1 type of objects. Each pair must consume at least one from this set. So we can show upper bound of sum-mx.
This upper bound can only be reached if we take one from mx, and one from the rest.
Therefore we can show if (mx >= sum-mx) answer is sum-mx.
Let’s consider it to be lesser. We are now considering the case where
mx < sum - mx.
Let’s take a pair from the largest two elements. Do a little bit of casework when 2*mx is just less than sum, there can only be 2 of mx, therefore we can reach a state where only one object is left.
Sure, say we want to check if we can make g groups from the array, then first convert array to a new array where ai = min(ai, g). Now I claim that the only necessary and sufficient condition to form g groups out of the array elements is that sum(array elements) >=k*g
I can prove this claim by finding a valid arrangement. Say above criteria is satisfied, then let us arrange element in a grid of g columns, and fill them row by row, one after another in the grid , obviously the number of rows would be at least k, and all columns are valid group partitions because no element in a column can repeat because it’s frequency is limited by g in the new array.
Hence we have a valid arrangement.