6 lines C++ O(nlogn)


#1
int Solution::solve(vector<int> &A, int B) {
    sort(A.begin(), A.end(), greater<int>());
    int prev=0;
    for(int i=0;i<A.size()-1;i++){
        if(prev+(A[i]-A[i+1])*(i+1)==B) return A[i+1];
        else if(prev+(A[i]-A[i+1])*(i+1)>B) return A[i]-=((B-prev)%(i+1)==0)?(B-prev)/(i+1):(B-prev)/(i+1)+1;
        prev+=(A[i]-A[i+1])*(i+1);}
}

#2

can you explain the approach and how it works


#3

Sorted decreasingly.

(A[i]-A[i+1])*(i+1) gives total number of wood cut if one choose,A[i+1] as the reference line(based on observation and dry run). How?

  • A[i]-A[i+1] gives the diff and it will be (i+1) times for every tree before it.
  1. If it becomes equal to B we directly return it
  2. If it is somehow greater than B then the answer needs to be in between A[i] and A[i+1]. You can run a for loop and check for every number in between them but since we have B, we know our destination we can also use this.
    • return A[i]-=((B-prev)%(i+1)==0)?(B-prev)/(i+1):(B-prev)/(i+1)+1
      What is it? B is the answer we want, A[i] is the upper limit , A[i+1] is the lower limit.
      1. Find the surplus wood needed (B-prev)/(i+1) and subtract it from A[i], but not every time (B-prev)/(i+1) is an integer can be a float as well , we can’t have half or quarter wood so , add 1 in it if it’s not completely divisible. (Zarurat se thoda zyada wood katega is case me)