贪心推公式
定义
贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，希望通过局部的最优选择来得到全局最优解的算法策略。
运用情况
- 问题具有最优子结构，即一个问题的最优解包含其子问题的最优解。
- 可以通过局部最优决策逐步推导到全局最优。
- 问题的选择策略相对明确且易于计算。
注意事项
- 贪心算法并不总是能得到全局最优解，可能会陷入局部最优。
- 对于一些复杂问题，需要谨慎验证其正确性。
- 可能需要对问题进行深入分析和特殊处理，以确保贪心策略的有效性。
解题思路
- 明确问题的目标和约束条件。
- 找出每一步的局部最优选择策略。
- 按照贪心策略逐步进行选择和计算。
- 验证最终结果是否符合预期，必要时进行调整或证明其正确性。
AcWing 125. 耍杂技的牛
题目描述
运行代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
int n;
PII cow[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int s, w;
scanf("%d%d", &w, &s);
cow[i] = {w + s, w};
}
sort(cow, cow + n);
int res = -2e9, sum = 0;
for (int i = 0; i < n; i ++ )
{
int s = cow[i].first - cow[i].second, w = cow[i].second;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}代码思路
- 定义了一个
PII类型来表示奶牛的信息（重量和强度之和以及重量）。 - 读取每头奶牛的重量和强度，计算并存储相关信息到数组
cow中。 - 对
cow数组按第一维（重量和强度之和）进行排序。 - 通过遍历计算每一步的风险值（当前总重量减去当前奶牛的强度），并更新最大风险值的最小值。
改进思路
- 错误处理：可以添加一些输入错误检查，例如检查输入的
n是否合理，以及输入的重量和强度值是否符合要求。 - 内存优化：如果可能的话，可以考虑动态分配
cow数组，以避免在不需要处理大量数据时浪费固定的较大内存空间。 - 代码结构优化：可以将数据读取、处理和输出的部分进一步划分清晰，提高代码的组织性。
- 性能微优化：虽然当前的排序和计算逻辑已经较为高效，但可以研究是否有更适合特定场景的优化方法。
- 使用 C++ 输入输出流：如前面提到的，可以将
scanf和printf替换为cin和cout，使代码风格更一致和现代。
改进代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
int n;
PII cow[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int s, w;
scanf("%d%d", &w, &s);
cow[i] = make_pair(w + s, w);
}
sort(cow, cow + n, [](const PII& a, const PII& b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
});
int res = -2e9, sum = 0;
for (int i = 0; i < n; i++) {
int s = cow[i].first - cow[i].second, w = cow[i].second;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}代码思路
- 首先定义了一些常量和数据结构，包括表示奶牛信息的
PII以及数组cow。 - 在
main函数中，通过scanf读取奶牛的数量n。 - 接着循环读取每头奶牛的重量
w和强度s，并将它们的和与重量组成PII存入cow数组。 - 使用自定义的比较函数对
cow数组进行排序，优先按和的大小排序，和相同时按重量大小排序。 - 初始化结果
res为一个极小值，以及总重量sum为 0 。 - 然后通过遍历排序后的数组，计算每一步的风险值（当前总重量减去当前奶牛的强度），并与当前的最大风险值比较更新，同时更新总重量。
- 最后将计算得到的最大风险值的最小值输出。