道阻且长，行则将至。
1、分割平衡字符串
1.1、题目描述
1221. 分割平衡字符串
在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例：
输入：s = “RLRRLLRLRL”
输出：4
解释：s 可以分割为 “RL”、“RRLL”、“RL”、“RL” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
1.2、题目分析
（1）明确题目中说明的
s
s
s一定是平衡字符串
（2）计数问题，遍历容器，遇到字符
L
L
L，和计数器加一，否则就减一，当和计数器为0的时候说明前面走过的字符串是一个平衡字符串，则答案计数器加一。
1.3、代码实现
class Solution {
public:
int balancedStringSplit(string s) {
int cnt = 0;
int sum = 0;
int i;
for(i = 0; i < s.size(); ++i){
sum += (s[i] == 'L' ? 1 : -1);
if(sum == 0){
++cnt;
}
}
return cnt;
}
};
2、最少操作数使数组递增
2.1、题目描述
1827. 最少操作数使数组递增
给你一个整数数组 nums（下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。
比方说，如果nums = [1,2,3] ，你可以选择增加 nums[1] 得到
nums = [1,3,3] 。
请你返回使 nums严格递增 的 最少 操作次数。
我们称数组 nums是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。
示例：
输入：nums = [1,1,1]
输出：3
解释：你可以进行如下操作：
1)增加 nums[2] ，数组变为 [1,1,2] 。
2)增加 nums[1] ，数组变为 [1,2,2] 。
3)增加 nums[2] ，数组变为 [1,2,3] 。
2.2、题目分析
（1）一般简单题进行模拟都可以做出来；
（2）维护一个变量pre记录已经完成递增任务的元素，维护一个答案变量ans。从第二个数开始遍历数组，当nums[i]小于pre时，就要更新当前的nums[i]为使递增的最小数(pre+1) （这里的更新只是思想上更新，并不是真的进行更新），并记录变化量(pre+1) - nums[i]，还要记得更新pre的值；当num[i大于pre的时候不需要进行操作，只要更新pre就好了。
2.3、代码实现
class Solution {
public:
int minOperations(vector<int>& nums) {
int pre = nums[0];
int i;
int ans = 0;
for(i = 1; i < nums.size(); ++i){
if(nums[i] <= pre){
ans += (pre+1) - nums[i];
pre += 1;
}
else{
pre = nums[i];
}
}
return ans;
}
};
3、卡车上的最大单元数
3.1、题目描述
1710. 卡车上的最大单元数
请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，
其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数。
示例：
输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
-1 个第一类的箱子，里面含 3 个单元。
-2 个第二类的箱子，每个里面含 2 个单元。
-3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
3.2、题目分析
（1）贪心的思想，每次都选取当前truckSize下包含最多单元的箱子；
（2）首先对二维数组按照进行第二个元素进行排序，然后遍历二维数组，利用贪心思想解决。
3.3、代码实现
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxes, int truckSize) {
sort(boxes.begin(), boxes.end(), [](const vector<int> v1, const vector<int> v2){
return v1[1] > v2[1];
});
int ans = 0;
int i, n = boxes.size();
int currNum = 0;
for(auto &box : boxes){
if(box[0] <= truckSize){
ans += box[0] * box[1];
truckSize -= box[0];
}
else{
ans += truckSize * box[1];
break;
}
}
return ans;
}
};
3.4、总结
（1）与其说是总结，不如说是对本题知识点的回顾吧；
（2）贪心思想：选取当前最优解得到的结果就是全局最优解，本题中就是每次都选取当前truckSize下可以包含的最大单元的那个箱子；
（3）排序操作，利用的是快排，时间复杂度是O（nlogn)，并且是自定义排序，是sort()函数的一个重载版本，第三个参数是一个 谓词 ，利用的是 lambda表达式 来实现的；
（4）谓词 是一个可调用的表达式，其返回结果是一个能被用做条件的值，具体用法可见《C++ Primer中文版（第五版）》约344页；
（5）、lambda表达式 表示一个可调用的代码单元，其 捕获列表 可以为空但不能省略，参数列表 可以省略，函数体 不可以省略，具体用法可见《C++ Primer中文版（第五版）》约345页.
4、打折购买糖果的最小开销
4.1、题目描述
2144. 打折购买糖果的最小开销
一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。
免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。
比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。
给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。
示例：
输入：cost = [1,2,3]
输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
4.2、题目分析
（1）为了减小开销，一定是要尽可能的获得更多 免费 的糖果，那么就是每买两颗，送一颗。
4.3、代码实现
class Solution {
public:
int minimumCost(vector<int>& cost) {
sort(cost.begin(), cost.end(), greater());
int i, n = cost.size();
int ans = 0;
for(i = 0; i < n; ++i){
ans += cost[i];
if(i+1 < n){
ans += cost[i+1];
}
else{
break;
}
i += 2;
}
return ans;
}
};
