BLDST - Solution || intuition

general
1

PROBLEM LINK:

Practice

DIFFICULTY:

1442

PREREQUISITES:

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();
}