贪心day6
文章目录
- 前言
- 打折购买糖果的最小开销
- 数组拆分
- 数组中最大数对和的最小值
- 救生艇
- 最大化数组的伟大值
- 求出最多标记下标
前言
💫你好,我是辰chen,本文旨在准备考研复试或就业
💫文章题目大多来自于 leetcode,当然也可能来自洛谷或其他刷题平台
💫欢迎大家的关注,我的博客主要关注于考研408以及AIoT的内容
🌟 仅给出C++版代码
以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新),欢迎大家的关注:
💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解
打折购买糖果的最小开销
题目链接:打折购买糖果的最小开销
C++版AC代码:
class Solution {
public:int minimumCost(vector<int>& cost) {sort(cost.begin(), cost.end(), greater<>());int res = 0;for (int i = 0; i < cost.size(); ++ i) {if ((i + 1) % 3)res += cost[i];}return res;}
};
数组拆分
题目链接:数组拆分
C++版AC代码:
class Solution {
public:int arrayPairSum(vector<int>& nums) {sort(nums.begin(), nums.end());int res = 0;for (int i = 0; i < nums.size(); ++ i ) if (!(i % 2))res += nums[i];return res;}
};
数组中最大数对和的最小值
题目链接:数组中最大数对和的最小值
C++版AC代码:
class Solution {
public:int minPairSum(vector<int>& nums) {sort(nums.begin(), nums.end());// 由贪心策略保证最小,然后去找最小对数和中的最大值int res = 0;for (int i = 0, j = nums.size() - 1; i < j; ++ i, -- j ) {int num = nums[i] + nums[j];res = max(res, num);}return res;}
};
救生艇
题目链接:救生艇
C++版AC代码:
class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(), people.end());int res = 0;for (int i = 0, j = people.size() - 1; i <= j; ++ i, -- j) {if (i == j) return res + 1;if (people[i] + people[j] > limit) -- i;res ++;}return res;}
};
最大化数组的伟大值
题目链接:最大化数组的伟大值
C++版AC代码:
class Solution {
public:int maximizeGreatness(vector<int>& nums) {sort(nums.begin(), nums.end());int res = 0;for (int i = 0, j = 0; j < nums.size(); ++ i, ++ j ) {while (j < nums.size() && nums[i] == nums[j]) j ++;if (j != nums.size()) res ++;}return res;}
};
求出最多标记下标
题目链接:求出最多标记下标
C++版AC代码:
class Solution {
public:int maxNumOfMarkedIndices(vector<int>& nums) {int n = nums.size();if (n == 1) return 0;sort(nums.begin(), nums.end());int res = 0;for (int i = 0, j = n / 2; i < n / 2 && j < n; ++ i, ++ j ) {while (j < n && 2 * nums[i] > nums[j]) ++ j;if (j < n) res += 2;}return res;}
};