D - Project Planning Editorial by en_translator

The original version of this problem was proposed by members of KEYENCE Corp.

Consider whether \(P\) or more projects can be made.

Let \(sum\) be the sum of \(\min(A_i,P)\) over \(i\,(1 \leq i \leq N)\). If \(P \times K > sum\), then obviously it is impossible to make \(P\) or more projects. In fact, we can prove that if \(P \times K \leq sum\), then we can make \(P\) or more projects.

If there are $K$ or more $i$ such that $A_i \geq P$, then obviously $P$ or more projects can be made. Otherwise, we can choose $K$ largest elements from $A_i$ to make one project, so that a project is made by decreasing $sum$ by at most $K$, so by induction it has been proved.

Therefore, we can do binary search for the solution to solve the problem.

When determining \(P\times K > sum\), be careful of the overflow.

Sample code (C++)

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

int main(){
    int n, k; cin >> n >> k;
    vector<long long> v(n);
    for(long long &x : v) cin >> x;
    long long ok = 0, ng = 1e18 / k;
    while(ng - ok > 1){
        long long md = (ok + ng) / 2, sum = 0;
        for(long long x : v) sum += min(x, md);
        if(sum >= k * md) ok = md;
        else ng = md;
    cout << ok << endl;

last update: