贪心算法
最优化问题定义：给定一组限制条件(constraint)和一个优化函数(optimization function)，求出一个可行解(feasible solution)，使得优化函数可能取得最优值，即最优解(optimal solution)，求解这样一个最优解的问题就称为最优化问题(optimi...
贪心算法|455.分发饼干
力扣题目链接 class Solution {public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); ...
经典贪心：最大延时最小问题
经典贪心：最大延时最小问题问题描述贪心方法试探短作业优先的尝试证明短作业优先的构造反例研究从反例不等式组推正确的贪心方法期限早优先法的证明问题描述贪心方法试探首先可以想到一些贪心方法，比如按执行时间排序做短作业优先的过程。我们分析它行不行，即尝试证明这种方法。短作业优先的尝试证明假设求出的处理序列有...
Codeforces 671A Recycling Bottles(贪心+思维)
题目链接：http://codeforces.com/problemset/problem/671/A题目大意：给你两个人的位置和一个箱子的位置，然后给出n个瓶子的位置，要求让至少一个人去捡瓶子放到箱子里面去，一次只能拿一个瓶子，求把全部瓶子捡完之后的距离总和最小。解题思路：开始有两个起点A，B。除...
【NOIP2015】斗地主（搜索，贪心）
题面戳我题解我原来也觉得是一道不可做的难题。。其实，，，很简单的啦。。。对于当前状态我们出牌的方式大致分为两类一类是不用考虑点数的，包括单张，对子，三带一等另一类就是需要考虑点数的，包括顺子等因此，每种状态下，首先考虑不用考虑点数的出牌方法尝试打完，更新打完。搜索的作用是考虑要考虑点数的出牌方法每次...
蓝桥杯23年第十四届省赛真题-填充|DFS，贪心
题目链接： 1.填充 - 蓝桥云课 (lanqiao.cn) 蓝桥杯2023年第十四届省赛真题-填充 - C语言网 (dotcpp.com) 说明： dfs就不再多说了，对于每个?都有0和1两个分支，数据范围是： 那么有m个 ?，时间复杂度就是 O()，会超时。蓝桥杯官网可以过35%的数据，暴力...
贪心算法问题
分发饼干-455 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i...
数据结构奇妙旅程之贪心算法
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不总是能得到最优解，但是对于很多问题，贪心算法可以得到最优解或近似最优解，并且算法效率较高。 下面通过一个经典的贪心算法问题——找零问题（...
贪心算法入门
简介 贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。也就是首先选取局部最优，从局部最优推出全局最优。 举例 有一堆不同面额的钞票，要从中取十次，要求最后的总金额最大。我们当然是每次都去取最大面额...
【Leetcode每日一刷】贪心算法| 45.跳跃游戏 II
1、45.跳跃游戏 II ????解题思路： 这题还是比【55.跳跃游戏】难一些的。第一个版本只是说，求跳跃的范围，覆盖到了终点即可。这题则是，能保证覆盖范围到达终点，求的是最少跳几次，跳到终点。 这题的话也是偏直觉，最好能一步到就好，一步到不了，两步能到吗？两步还到不了，三步呢？听起来是不是还挺...
力扣日记3.11-【贪心算法篇】455. 分发饼干
力扣日记：【贪心算法篇】455. 分发饼干 日期：2024.3.11 参考：代码随想录、力扣 455. 分发饼干 题目描述 难度：简单 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口...
贪心算法
贪心算法： 在每一步选择中都采取当前状态下的最优决策（局部最优）。并希望由此导致的最终结果是全局最优。贪心算法与一般的搜索，以及动态规划相比，不同之处在于：它不对整个状态空间进行遍历或计算，而是始终按照局部最优选择执行下去，不再回头。因为这个特性，贪心算法不一定能得到正确的结果，除非可以证明，按...
PAT 贪心、二分、双指针专题
1023 组个最小数 给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。 现给定数字，请编写程序输出能够组成的最小的数。 ...
贪心 Leetcode 763 划分字母区间
划分字母区间 Leetcode 763 学习记录自代码随想录 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 示例 1： 输入：s =...
【C++】贪心算法
贪心算法（Greedy Algorithm）是一种基于贪心策略的算法，它在每一步选择中都采取当前状态下最优的选择，以希望最终得到全局最优解。贪心算法通常适用于满足最优子结构性质的问题，即问题的最优解可以通过其子问题的最优解来构造。 贪心算法的基本思路是： 定义问题的目标函数，即要最大化或最小化的目标...
贪心算法（算法竞赛、蓝桥杯）--修理牛棚
1、B站视频链接：A27 贪心算法 P1209 [USACO1.3] 修理牛棚_哔哩哔哩_bilibili 题目链接：[USACO1.3] 修理牛棚 Barn Repair - 洛谷 #include <bits/stdc++.h> using namespace std;cons...
力扣 第 386 场周赛 解题报告 | 反悔贪心
力扣 第 386 场周赛 解题报告 | 反悔贪心 前言 整体评价 前两天发烧，今天才补完题（非常惭愧）第三题的二分不容易想到，第四题的 “反悔堆” 这种思想值得学习。 T1 分割数组 思路：通过哈希表保证不存在出现两次以上的数即可。 时间复杂度： ...
贪心算法：汽车加油问题
1.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少请写出该...
数据结构与算法——贪心算法
应用场景-集合覆盖问题贪心算法可以解决很多场景的问题，这里以集合覆盖问题为例。假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所...
算法训练营day30，贪心算法4
import "sort" // 860. 柠檬水找零 func lemonadeChange(bills []int) bool { //如果最开始就大于5元，肯定无法找零直接返回false if len(bills) > 0 && bills[0] > 5 ...