1626. Salary Adjustment

Given a list of salaries, find the smallest cap which makes the sum of adjusted salary be equal to or larger than the given target. cap is defined as: if the current salary is smaller than cap, then cap is used as the new salary, otherwise keep the original salary

The length of the list does not exceed $100000$
The salaries do not exceed $10000$

Have you met this question in a real interview?  

Example

Example 1：

Give `a=[1,2,3,4],target=13`,
return `3`.
Input:
1 2 3 4
13
Output:3

Explanation:
If cap=3, the list will change into [3,3,3,4].

Example 2:

Give `a=[1,2,3,4],target=16`,
return `4`.
Input:
1 2 3 4
16
Output:4

Explanation:
If cap=4, the list will change into [4,4,4,4].

Code(Language:C++)

class Solution {
public:
    /**
     * @param a: the list of salary
     * @param target: the target of the sum
     * @return: the cap it should be
     */
    int getCap(vector<int> &a, int target) {
        // Write your code here.
        int sum = 0; 
        int minV = INT_MAX;
        for(int i = 0; i < a.size(); i++){
            sum += a[i];
            minV = min(minV, a[i]); 
        }
        // binary search 
        if(sum >= target){
            return minV; 
        }
        int start = minV;
        int end = target / a.size() + 1; 
        while(start + 1 < end){
            int mid = start + (end - start) / 2; 
            int adjSum = getSum(a, mid);
            if(adjSum <= target){
                start = mid; 
            }
            else{
                end = mid; 
            }
        }
        if(getSum(a, start) >= target){
            return start; 
        }
        else{
            return end; 
        }
    }
    int getSum(vector<int> &a, int cap){
        int sum = 0;
        for(auto i : a){
            sum += (i >= cap ? i : cap); 
        }
        return sum; 
    }
};

Code(Language:C++)

class Solution {
public:
    /**
     * @param a: the list of salary
     * @param target: the target of the sum
     * @return: the cap it should be
     */
    int getCap(vector<int> &a, int target) {
        // Write your code here.
        int sum = 0; 
        int minV = INT_MAX;
        for(int i = 0; i < a.size(); i++){
            sum += a[i];
            minV = min(minV, a[i]); 
        }
        // binary search 
        if(sum >= target){
            return minV; 
        }
        int start = minV;
        int end = target / a.size() + 1; 
        while(start + 1 < end){
            int mid = start + (end - start) / 2; 
            int adjSum = getSum(a, mid);
            if(adjSum <= target){
                start = mid; 
            }
            else{
                end = mid; 
            }
        }
        if(getSum(a, start) >= target){
            return start; 
        }
        else{
            return end; 
        }
    }
    int getSum(vector<int> &a, int cap){
        int sum = 0;
        for(auto i : a){
            sum += (i >= cap ? i : cap); 
        }
        return sum; 
    }
};