tags: Weekly Contest

Weekly Contest 388

3074. Apple Redistribution into Boxes (Easy)

限制 :

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50

Solution

先將所有蘋果加起來，再由最大的籃子開始放，放到蘋果都空了就得到答案。

時間複雜度:

$O(nlogn)$

空間複雜度:

$O(1)$

程式碼:

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        long total_apple = 0;
        for(auto& apple_i : apple)
        { 
            total_apple+= apple_i;
        }
        // cout << total_apple <<'\n';
        
        int result = 0;
        sort(capacity.begin(), capacity.end());
        for(int i = capacity.size()-1 ; i>=0 && total_apple > 0; i--)
        {
            result+=1;
            total_apple -= capacity[i];
        }
        return result;
    }
};

3075. Maximize Happiness of Selected Children (Medium)

限制 :

• 1 <= n == happiness.length <= 2 * 105
• 1 <= happiness[i] <= 108
• 1 <= k <= n

Solution

這題的演算法是把k個小孩的幸福度加起來，但因為小孩會隨著被挑的順序越後面，幸福度越低，所以必須減掉次數才是真正的幸福度。

時間複雜度:

$O(nlogn)$

空間複雜度:

$O(1)$

程式碼:

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end(), greater<int>());
        long result = 0;
        for(int i=0;i<k;i++)
        {
            int value = happiness[i]-i;
            if(value<= 0) break;
            result += value;
        }
        return result;
    }
};

3076. Shortest Uncommon Substring in an Array(Medium)

限制 :

• 104

Solution

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼:

3077. Maximum Strength of K Disjoint Subarrays(Hard)

限制 :

• 104

Solution

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼: