文章目录
前言
一、贪心
二、AcWing 125. 耍杂技的牛
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：贪心——推公式，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、贪心
贪心：利益最大化，即找到最优的情况，贪心问题难在证明，即你可能能推断出这个题目的正确解法，但是这个解法下为什么就是最优解不好证明。
二、AcWing 125. 耍杂技的牛
本题链接：AcWing 125. 耍杂技的牛
本博客给出本题截图
本题分析
用到了pair，pair的详细用法见博客：（先鸽）
排序方法是按照重量和强壮从小到大进行排序，重量和强壮之和越小越放到上面.
AC代码
#include <algorithm> #include <cstdio> using namespace std; typedef pair<int, int> PII; const int N = 50010; PII cow[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int w, s; 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 ++ ) { auto t = cow[i]; int s = t.first - t.second, w = t.second; res = max(res, sum - s); sum += w; } printf("%d", res); return 0; }
三、时间复杂度
关于贪心——推公式的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
