算法【贪心经典题目专题4】

题目一

测试链接：1675. 数组的最小偏移量 - 力扣（LeetCode）

分析：可以观察出，如果元素是奇数，那么只有两种可能，即奇数本身和奇数乘2而偶数可以震荡。所以可以将奇数扩大两倍，偶数不变放入一个有序表，每次拿有序表的最大值减最小值，求得偏移量，然后将最大值除以2直到最大值为奇数退出循环，此时记录的偏移量就是最小偏移量。代码如下。

class Solution { public: int minimumDeviation(vector<int>& nums) { int length = nums.size(); multiset<int> table; for(int i = 0;i < length;++i){ if(nums[i] % 2 == 1){ table.insert(nums[i] * 2); }else{ table.insert(nums[i]); } } set<int>::iterator minValue, maxValue; int ans = -((1 << 31) + 1); int temp; while (true) { minValue = table.begin(); maxValue = table.end(); --maxValue; ans = min(ans, (*maxValue) - (*minValue)); if((*maxValue) % 2 == 1){ break; } temp = (*maxValue); table.erase(maxValue); table.insert(temp/2); } return ans; } };

题目二

测试链接：781. 森林中的兔子 - 力扣（LeetCode）

分析：对相同答案做词频统计，对每一个词频计算兔子的最少数量相加即是答案。代码如下。

class Solution { public: int numRabbits(vector<int>& answers) { int length = answers.size(); unordered_map<int, int> table; unordered_map<int, int>::iterator pos; for(int i = 0;i < length;++i){ pos = table.find(answers[i]); if(pos == table.end()){ table.insert(pair<int, int>(answers[i], 1)); }else{ ++((*pos).second); } } int ans = 0; for(unordered_map<int, int>::iterator it = table.begin();it != table.end();++it){ ans += (((*it).second + (*it).first) / ((*it).first + 1)) * ((*it).first + 1); } return ans; } };

题目三

测试链接：2449. 使数组相似的最少操作次数 - 力扣（LeetCode）

分析：注意到操作并不会改变数字的奇偶性，所以可以将nums数组和target数组中的奇数和偶数分组，并且nums数组中的奇数个数等于target数组中的奇数个数，nums数组中的偶数个数等于target数组中的偶数个数，并且对这四个数组进行从小到大排序。奇数数组中相同下标即是对应的变换，偶数数组也是一样，将所有变换的差值相加除以一次变换可以弥补的差值4就是答案。代码如下。

class Solution { public: long long makeSimilar(vector<int>& nums, vector<int>& target) { vector<int> nums_odd; vector<int> nums_even; vector<int> target_odd; vector<int> target_even; for(int i = 0;i < nums.size();++i){ if(nums[i] % 2 == 1){ nums_odd.push_back(nums[i]); }else{ nums_even.push_back(nums[i]); } } for(int i = 0;i < target.size();++i){ if(target[i] % 2 == 1){ target_odd.push_back(target[i]); }else{ target_even.push_back(target[i]); } } sort(nums_odd.begin(), nums_odd.end()); sort(nums_even.begin(), nums_even.end()); sort(target_odd.begin(), target_odd.end()); sort(target_even.begin(), target_even.end()); long long ans = 0; for(int i = 0;i < nums_odd.size();++i){ ans += abs(nums_odd[i] - target_odd[i]); } for(int i = 0;i < nums_even.size();++i){ ans += abs(nums_even[i] - target_even[i]); } return ans / 4; } };

题目四

测试链接：知识竞赛_牛客题霸_牛客网

分析：可以看出，x和y是否除以2对于中间过程并不影响，所以可以先求出答案之后再除以2。首先对员工进行排序，按员工推理能力值减阅读能力值的绝对值从小到大进行排序。遍历到某一员工时，如果当前员工推理值较小，则加上之前员工中最大的推理值；如果当前员工阅读值较小，则加上之前员工中最大的阅读值，更新答案，最后返回时，答案除以2。代码如下。

#include <iostream> #include <algorithm> #include <vector> using namespace std; int n; struct Worker { int ai; int bi; }; int main(void){ scanf("%d", &n); vector<Worker> worker; worker.reserve(n); for(int i = 0;i < n;++i){ Worker temp; scanf("%d%d", &temp.ai, &temp.bi); worker.push_back(temp); } sort(worker.begin(), worker.end(), [](Worker& w1, Worker& w2){ return abs(w1.ai - w1.bi) < abs(w2.ai - w2.bi); }); int ans = 0; int max_ai = 0; int max_bi = 0; Worker w; for(int i = 0;i < n;++i){ w = worker[i]; if(w.ai > w.bi){ ans = max(ans, w.bi + max_bi); }else{ ans = max(ans, w.ai + max_ai); } max_ai = max(max_ai, w.ai); max_bi = max(max_bi, w.bi); } printf("%.1f", (float)ans / 2); return 0; }

题目六

测试链接：871. 最低加油次数 - 力扣（LeetCode）

分析：用一个大根堆维护可以加油的加油站，当当前无法到达终点时，加油量最大的那个加油站，如果还是无法到达终点更新可以加油的加油站，加油量最大的加油站，循环往复。代码如下。

class Solution { public: int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) { if(startFuel >= target){ return 0; } if((stations.size() == 0 && startFuel <= target) || startFuel < stations[0][0]){ return -1; } int length = stations.size(); auto cmp = [](int& a, int& b){ return a < b; }; priority_queue<int, vector<int>, decltype(cmp)> p(cmp); int index = 0; for(;index < length;++index){ if(stations[index][0] <= startFuel){ p.push(stations[index][1]); }else{ break; } } int ans = 0; while (!p.empty()) { startFuel += p.top(); ++ans; p.pop(); if(startFuel >= target){ break; } for(;index < length;++index){ if(stations[index][0] <= startFuel){ p.push(stations[index][1]); }else{ break; } } } return startFuel >= target ? ans : -1; } };