贪心day1

前言

💫你好，我是辰chen，本文旨在准备考研复试或就业
💫文章题目大多来自于 leetcode，当然也可能来自洛谷或其他刷题平台
💫欢迎大家的关注，我的博客主要关注于考研408以及AIoT的内容
🌟 仅给出C++版代码

以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)，欢迎大家的关注：

💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解

雪糕的最大数量

题目链接：雪糕的最大数量

C++版AC代码：

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int res = 0;
        for (int i = 0; i < costs.size(); ++ i) 
            if (coins >= costs[i]) 
                res ++, coins -= costs[i];
            else break;

        return res;
    }
};

重新分装苹果

题目链接：重新分装苹果

C++版AC代码：

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        sort(capacity.begin(), capacity.end());
        reverse(capacity.begin(), capacity.end());
        
        int num = 0;
        for (int i = 0; i < apple.size(); ++ i)
            num += apple[i];

        int res = 0;
        for (int i = 0; i < capacity.size(); ++ i) {
            num -= capacity[i];
            res ++;
            if (num <= 0) break;
        }
            
        return res;
    }
};

装满石头的背包的最大数量

题目链接：装满石头的背包的最大数量

C++版AC代码：

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        for (int i = 0; i < capacity.size(); ++ i) 
            capacity[i] -= rocks[i];
        
        sort(capacity.begin(), capacity.end());
        int res = 0;
        for (int i = 0; i < capacity.size(); ++ i) 
            if (additionalRocks >= capacity[i]) {
                additionalRocks -= capacity[i];
                res ++;
            }
        
        return res;
    }
};

K 次取反后最大化的数组和

题目链接：K 次取反后最大化的数组和

C++版AC代码：

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++ i) 
            if (k && nums[i] < 0) {
                k --;
                nums[i] = -nums[i];
            }else {
                break;
            }
        sort(nums.begin(), nums.end());
        if (k % 2) nums[0] = -nums[0];

        int res = 0;
        for (int i = 0; i <nums.size(); ++ i)
            res += nums[i];
        
        return res;
    }
};

不同整数的最少数目

题目链接：不同整数的最少数目

C++版AC代码：

class Solution {
public:
    int cnt[100010];
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        map<int, int> m;
        for (int i = 0; i < arr.size(); ++ i) m[arr[i]] ++;

        int num = 0;
        for (auto i = m.begin(); i != m.end(); ++ i) cnt[num ++] = i -> second;
        sort(cnt, cnt + num);

        for (int i = 0; i < num; ++ i) 
            if (k >= cnt[i]) {
                k -= cnt[i];
            }else {
                return num - i;
            }
        return 0;
    }
};