2226. Maximum Candies Allocated to K Children

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    long long isValid(vector<int> & candies, long long t){
        // 給定糖果，假設每人t個，可以分給多少人
       long long count = 0;
        for(int c:candies){
            count += c/t;
        }
        return count;
        
    }
    int maximumCandies(vector<int>& candies, long long k) {
        long long l = 1, r = LONG_MIN;
        for(int c:candies){
            r = max(r, (long long)c);
        }
        
        // binary search
        int ret= 0;
        while(l<=r){
            long long mid = l +(r-l)/2;
            long long eval = isValid(candies, mid);
            cout<<l<<" "<<r<<endl;
            cout<<"假設每人可以分到"<<mid<<"顆糖果\t可以分給 "<<eval<<" 人"<<endl;
            if(eval < k) r = mid-1;
            else if(eval>=k) {
                ret = mid;
                l = mid+1;
            }
            
        }
        return ret;
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(1)