21 Days Training // Day (15 2/3)

C. Flush

To solve this problem, we need to use the pigeonhole principle.
Suppose that you need to select K tea bags with the same flavor.
Then, in order to prevent you form achieving this goal, he will choose K-1 tea bags for each flavor.
In this case, no matter how you choose tea bags, you cannot select K tea bags with the same flavor.
However, when the dealer selected tea bags as above, as soon as he choose one more tea bag, you can immediately achieve your goal.

So, the problem is : How many tea bags will be selected in step 1?

If the number of the tea bags of one flavor is smaller than K , selecting them all still statisfies the condition.
If the number of the tea bags of one flavor is greater than or equals to K , you can only select K-1 bags.

You can use upper_bound to finc the number of flavors that satisifes condition 1.

Code :

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

int main() {
    long long N, Q;cin >> N >> Q;
    long long A[N], pfx[N+1];
    for (long long i=0;i<N;i++) cin >> A[i];
    pfx[0] = 0;
    sort(A, A+N);
    for (long long i=1;i<=N;i++) pfx[i] = pfx[i-1] + A[i-1];

    for (long long i=0;i<Q;i++) {
        long long B;cin >> B;
        if (B>A[N-1]) {
            cout << -1 << endl;
            continue;
        }
        long long MN=lower_bound(A, A+N, B)-A;
        //printf("DX : %d\n", MN);
        cout << pfx[MN]+(N-MN)*(B-1)+1 << endl;
    }
    return 0;
}

Notice that the answer may exceed the limit of int32.
My experience :
1st Submission

(1)