思路 这道题其实主要的难点是如何排序。 排序之后贪心就非常简单了。 考虑贪心邻项交换 设 si=∏j=0iajs_i=\prod\limits_{j=0}^{i}a_jsi?=j=0∏i?aj?。 首先考虑交换前，第 iii 个上的值是 si?1bi\frac {s_{i-1}}{b_i}bi?si?1??，第 i+1i+1i+1个 是 si?1aibi+1\frac {s_{i-1}\times a_i}{b_{i+1}}bi+1?si?1?ai?? ans1=max?(si?1bi,si?1aibi+1)ans_1=\max(\frac {s_{i-1}}{b_i},\frac {s_{i-1}\times a_i}{b_{i+1}})ans1?=max(bi?si...
本文 https://github.com/youngyangyang04/leetcode-master 已经收录，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库，有空看一看一定会有所收获，如果对你有帮助也给一个star支持一下吧！周一 在贪心算法：用最少数量的箭引爆气球中，我们开始讲解了重叠区间问题，用最少的弓箭射爆所有气球，其本质就是找到最大的重叠区间。 按照左边界经行排序后，如果气球重叠了，重叠气球中右边边界的最...
贪心算法的套路：一定会有一个排序。哈夫曼编码，贪心算法，压缩算法。最短路径 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 贪心算法其最重要的两个点就是： 贪心策略：排序 通过局部最优解能够得到全局最优解 一般通过以下问题就可以通过贪心算法解决： 1.针对某个问题有限制值，以及有一个期望的最好结果，...
452. 用最少数量的箭引爆气球 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的...
1.贪心算法的基本概念贪心算法通过一系列的选择来得到问题的解，所做的每个选择都是当前状态下局部最好的选择，即贪心选择2. 贪心算法与动态规划算法的比较贪心算法与动太规划算法都要求问题具有最优子结构性质，这是两个算法的一个共同点， 贪心选择性质是指：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别3.贪心算法的基本算法...
背包问题----区分于0/1背包问题 【问题】给定n个物品和一个容量为c的背包，物品 i 的重量是w[i]，其价值为v[i]，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大。注意和0/1背包问题的区别，在背包问题中，可以将某种物品的一步分装入背包中，但不可以重复装入。【 思路 】背包问题与0/1背包类似，所不同的是在选择物品 i (1<= i <=n）装入背包时，可以选择一部分，而不一定要全部装入背包。所以可以对物品按w[...
假设有N项物品，大小分别为s ?1 ?? 、s ?2 ?? 、…、s ?i ?? 、…、s ?N ?? ，其中s ?i ?? 为满足1≤s ?i ?? ≤100的整数。要把这些物品装入到容量为100的一批箱子（序号1-N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。 输入格式： 输入第一行给出物品个数N（≤1000）；第二行给出N个正...
本文 https://github.com/youngyangyang04/leetcode-master 已经收录，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库，有空看一看一定会有所收获，如果对你有帮助也给一个star支持一下吧！860.柠檬水找零 题目链接：https://leetcode-cn.com/problems/lemonade-change/ 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾...
终于到周末了，明明是特别喜欢看电影。他想在一天内尽量多的看到完整的多部电影。 现在他把他喜欢的电影的播放时间表给你，希望你能帮他合理安排。 输入格式: 输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示明明喜欢的电影的总数。 接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个电影的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。 当n=0时，输入结束。 输出格式: 对于每组输入，...
用最少数量的箭引爆气球在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭...
核心思想 在对问题进行求解时，每步都选择局部最优解，希望最终可以得到全局最优解。 （贪心算法最终所得的结果不一定是全局最优解，但确是近似的最优解。）经典问题——集合覆盖问题 有n个集合，每个集合都含有若干个元素，从中找出m个集合，要求包含n个集合中所有的元素且m最小。 一般解决方法： （1）列出n个集合的所有组合方案，因为每个集合都可以包含或不包含，所以共有2n2^n2n种组合方案。 （2）在这些组合方案中，找出含有...
跳跃游戏给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最...
分发饼干假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 示例 1: 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个...
题目描述 键盘输入一个高精度的正整数 NN（不超过 250250 位），去掉其中任意 kk 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 NN 和 kk，寻找一种方案使得剩下的数字组成的新数最小。 输入格式 n（高精度的正整数 )。 k（需要删除的数字个数 )。 输出格式 最后剩下的最小数。 输入样例 175438 4输出样例 13#include<bits/stdc++.h> using namespace std;int main() {string a; int n,t,cnt=0;cin>>a>>n...
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。 注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 ...