Practice

1442

None

# PROBLEM:

There are N empty boxes, and A_i balls of color i (for 1 \leq i \leq M).
The balls must be distributed to the boxes such that:

• Every ball is placed in a box
• Each box contains balls of distinct colors

Find the minimum number of boxes that have balls of all M colors.

# EXPLANATION:

A box can either be good or bad. For the box to become bad, it should have M balls of different colors in the box. If we place M-1 balls of different colors in a box then the box will still be good. So we first make all the boxes good. We can distribute (M-1) * N balls without making any box bad. So the balls that are left i.e. \Sigma A_i - (M-1)*N will make the box bad. Since this value can be negative so we will take the maximum of it with zero.

# TIME COMPLEXITY

\mathcal{O}(M) per testcase.

# CODE:

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

class Solution {
int testcase = 0;
void solveOne() {
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int &x : a) {
cin >> x;
}
int sum = accumulate(a.begin(), a.end(), 0);
cout << max(sum - (m - 1) * n, 0);
}

public:
Solution(int tc) : testcase(tc) {}
void solve() {
while (testcase-- > 0) {
solveOne();
cout << "\n";
}
}
};

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tc = 1;
cin >> tc;
Solution sol(tc);
sol.solve();
}