Contest Duration: - (local time) (100 minutes) Back to Home

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.

Proof
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;
}

posted:
last update: