【算法学习之路】5.贪心算法

贪心算法 前言一.什么是贪心算法二.例题1.合并果子2.跳跳！3. 老鼠和奶酪

前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

一.什么是贪心算法

总是只看眼前，并不考虑以后可能造成的影响，将一个最优决策变成多步决策过程，并在每步总是做出当前看起来是最好的选择，它所做的选择只是在某种意义上的局部最优选择可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

二.例题 1.合并果子

洛谷P1090 [NOIP 2004 提高组] 合并果子

//使用优先队列解决 #include <iostream> #include <queue> #include <algorithm> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>>p;//定义一个优先队列且为小顶堆 int n; cin >> n; for (int i = 0; i < n; i++) {//将每个数据填入优先队列 int a; cin >> a; p.push(a); } int sum = 0;//需要体力的总值 while (p.size() > 1) {//当元素只有一个的时候意味着结束 //将最小的两个取出来进行合并 int first = p.top(); p.pop(); int last = p.top(); p.pop(); //将合并的结果填入优先队列 int t = first + last; sum += t; p.push(t); } cout << sum; return 0; } 2.跳跳！

洛谷P4995 跳跳！

//用列表解决 #include <iostream> #include <list> #include <cstdlib> using namespace std; int main() { list<long long> s;//由于数据过大，需要用到long long int n; cin >> n; for (int i = 0; i < n; i++) {//将所有数据填入列表 long long a; cin >> a; s.push_back(a); } s.sort();//将列表进行排序 long long sum = 0;//消耗的总体力值 long long first = 0; long long last = 0; while (s.size() > 0) {//当没有元素结束 last = s.back(); s.pop_back(); sum += (last - first) * (last - first); if (s.size() > 0) {//如果元素是奇数 first = s.front(); s.pop_front(); sum += (last - first) * (last - first); } } cout << sum; return 0; } 3. 老鼠和奶酪

力扣2611. 老鼠和奶酪

static int cmp(const void* pa, const void* pb) {//比较函数 return *(int *)pa - *(int *)pb; } int miceAndCheese(int* reward1, int reward1Size, int* reward2, int reward2Size, int k) { int sum = 0;//总值 int diff[reward1Size];//两只老鼠的差值 for(int i = 0; i < reward1Size; i++){ sum += reward2[i];//先将所有的奶酪给第二只老鼠吃 diff[i] = reward1[i] - reward2[i];//计算出两个老鼠的差值 } qsort(diff, reward1Size, sizeof(int), cmp);//将差值排序 for(int i = 1; i <= k; i++){ sum += diff[reward1Size - i];//将差值填入总数 } return sum; }