贪心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;
}
};
原文地址:https://blog.csdn.net/qq_52156445/article/details/142992712
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!