思路： 题目的主要信息：  的花费是 问数组a中所有元素全部相加求和的花费  假如按照顺序相加我们所需的花费就是： 也即答案为乘上一个数，因此我们不用管，最后乘上它即可。要想让后方这些数字相加和最小，我们可以用哈夫曼树的思想，每次寻找最小的两个数字相加，然后将和放入这些未加数字中，再比较，再找出最小的两个数字相加，这样花费将是最小的，哈夫曼树的构建如下图：  方法一：优先队列（小顶堆）具体做法：利用priority_queue模拟小顶堆，入堆后顶部都是最小的元素，每次只要弹出两个堆中元素，然后将结果再加入堆中排序即可。 class Solution { public: long long so...

思路： 题目的主要信息：  数组a长度为n，且数字不重复，数组长度不为0 对于数组的某个连续子数组而言，区间内的最大值与次大值的异或值为该子数组的魔法值 整个数组中所有子区间的魔法值的最大值就是数组的魔法值，求这个值  方法一：数组模拟单调队列具体做法：如果我们找到了一个区间的最大值想要再找到次大值需要再次遍历一遍，很麻烦，于是我们可以考虑用一个单调队列保存数组内的值，使之成递减序，而我们每次遇到一个元素就可以在单调队列中往前寻找比更大的一个数，这其中的区间这两个数就是最大值和次大值，我们取异或然后更新答案即可。这是往后遍历的情况，但是我们不能保证最大值一定出现次大值前面，因为单调队列中保存的...

思路： 题目的主要信息：  数组A表示N条鱼各自的大小，对于每条鱼，它在每一次操作时会吃掉右边比自己小的第一条鱼 吃的操作是同时，即如果有一连串递减子序列，只会剩下子序列最左边的元素 问要多少次操作，鱼的数量就不会变了  方法一：暴力模拟法具体做法：我们可以模拟这个吃的过程。首先按照上面说到的每次第一条鱼不会被吃，会被留下来，后续的鱼如果左边的鱼小于右边的鱼，右边的鱼才可以留下来，将留下来的鱼都按照顺序加入一个新的数组，然后将原数组更新为新数组，继续进行这样的操作，直到新旧数组的元素个数相等，即代表一次操作没有任何的吃掉行为，可以结束。 class Solution { public: int...

思路： 题目的主要信息：  n个房间，n-1条通道连通，这就是一棵树 树每个节点值记录在x数组 去掉树的一些边，使之成为k个子树，且每个子树的节点值和大于等于m，问可行性  方法一：dfs具体做法：主体思路是，将树分成每个部分刚好大于等于m，看是否有大于等于k个子树。首先构建图，利用深度优先搜索自底向上将每个子树的节点值往上累加，每次遇到累加和大于等于m时，往上加的就归零，相当于切断该子树往上的边，同时计数k减一，最后检查k是否小于等于0即可。 class Solution { public: //深度优先搜索函数相加和大于等于m即k减一 int dfs(vector<vector&lt...

思路： 题目的主要信息：  n个节点，n-1条边使之连通，这就是一棵树（注意不一定是二叉树），每条边代表距离为1 一共m次污染，每次发生在数组元素x[i]，影响范围是与发生点距离不超过y[i]（发生点视为距离为0），影响范围所有节点污染指数增加z[i] 污染指数初始值全部为0，求m次污染发生后，每个节点的污染指数  方法一：排序+距离模拟具体做法：我们可以对所有污染的影响距离进行排序，然后以影响范围最远的开始，依次递减，直到为0，我们用三个数组相互交替记录之前增加的污染指数和本轮增加的污染指数，最后将二者相加即是结果。计算本轮的时候需要注意不能当前的距离不能小于本轮的距离，否则会重复，此时应该...

思路： 题目的主要信息：  数组a有n个元素，将其分成k个连续的子序列 求最大的每个子序列和最小值  方法一：暴力判断具体做法：我们都知道子序列和最小值绝不会超过数组a的元素和sum，同时分成k组后，也绝不会大于，因此我们可以从开始，依次递减判断每个数是否成为k组连续子序列和的最小值。在判断的时候，我们累加a数组中的元素，每次超过我们要判断的数时，就计数代表一段，同时累加归零往后重新累加。如果最后我们的分段数大于等于m，即认为这是可行的分段，也是当前找到的最大最小和。 class Solution { public: bool judge(vector<int>& a, i...

思路： 题目的主要信息：  求最少需要布置x个导弹系统 其中每个导弹系统每天只能发射一枚导弹，但是我们一天总计要发射至少M枚 导弹系统一经发射，必须连续发射A天，且需要休息B天不能发射 导弹系统在交接的时候，至少需要有一个导弹系统是可以工作的  方法一：暴力模拟法具体做法：首先如果，我们只需要安排M个导弹系统在前A天发射，M个导弹系统在后B天发射，但是因为要在交接时前面的还没休息好，如果至少需要有一个导弹系统可以发射，因此我们还要多备M个，因此这种情况是个系统；再来，这种情况下导弹需要交接的时候前面已经休息好了，可以直接使用，因此我们可以不用多备，结果是个系统；最后如果，我们可以直接暴力模拟一...

思路： 题目的主要信息：  数组a表示n个异次元空间的暗物质数量，每天每个异次元空间的暗物质数量会增加d数组中对应元素的值 可以选择冻结空间使之每天不再增加，也可以选择接触冻结 如果异次元空间的暗物质数量大于等于P，会对P取余，P一定为质数 最少可以在第几天的晚上有不少于m个异次元空间有刚好k个暗物质  方法一：二分法（超时）具体做法：每个空间的增加天数最多次，即到天之内不断取模，它必定会增加到刚好k个暗物质。我们可以从到使用二分法，每次检查中间值mid是否满足m个异次元空间在mid天内刚好到达k个暗物质，若可以则缩小右界，若是不行则缩小扩大左界。 class Solution { publi...

思路： 题目的主要信息：  一个长度为n的正整数数组，从中选取长度大于等于k的连续子序列 “中数”为最大的整数x，使得序列中至少一半的数字大于等于x 求所有选出来的子序列中最大中数  方法一：暴力构造+优先队列具体做法：我们遍历两遍数组，找到每个不小于k的子序列的两个端点坐标。从一个端点遍历到另一个端点，利用优先队列（默认大根堆）记录这个子序列，然后先弹出队列总数一半少一个的元素（这里的一半要分奇偶讨论），下一个数就是我们要的中数。然后比较每次每个子序列的中数，找到最大值。 class Solution { public: int solve(int n, int k, vector<i...

思路： 题目的主要信息：  现有n堆石子，每堆数量记录在数组a 可以对任意石子数大于1的堆分裂成两堆数量大于等于1的石子 现需要分裂成m堆石子()，问这m堆石子最小值最大可以是多少？  方法一：暴力法具体做法：我们都知道分裂只会让石子更少，因此最小值一定小于等于分裂前数组最开始的最小值。因此我们从数组分裂前的最小值开始依次往下找，直到为最小值为1.每次找i是否可行的时候，我们查看是否有大于等于m堆石子，其中每堆数量都是不小于i。某堆数量除以i向下取整就得到原始的每堆可以分成的数量，只需要检查将数量累加查看是否大于等于m即可。 class Solution { public: int solve...

思路： 题目的主要信息：  数组A表示n只怪兽的血量 攻击第只怪兽时，必须同时打到第和第只怪兽，每次攻击一滴血（没有这三只怪兽则无法攻击） 怪兽血量归零后还可以继续受到攻击 需要使用最少多少次组合拳才能把所有怪兽打死，如果打不死请输出-1  方法一：贪心+ 迭代具体做法：首先，组合拳一定要打至少3只怪兽，怪兽数量小于3，无法击败；其次， 攻击第只怪兽时，必须同时打到第和第只怪兽，因此怪兽数量一定是奇数，偶数还是无法击败。然后我们利用贪心思想，从中间只怪兽()开始，因为打中间怪兽时我们会同时攻击到最后两只怪兽，我们的目的就是优先解决最后的怪兽，选出最后两只的最大者，打这么多次便可以将这两只怪兽解...

思路： 题目的主要信息：  a数组表示每天的鸡肉汉堡数，b数组表示每天的牛肉汉堡数 一共n天，每天吃的汉堡数都不相同 要求吃尽可能多的总数汉堡的情况下又要尽可能少吃牛肉汉堡（优先满足前者条件） 求最少要吃的牛肉汉堡数  利用贪心思想，安排每天的汉堡数量，尽可能多地吃汉堡，然后再讨论少吃牛肉汉堡的情况。 方法一：双有序列表具体做法：要想做到吃最多的汉堡，我们就要对每天的汉堡总书进行排序，因为每天吃的数量不同，我们要保证最多的数量给到汉堡最多的天数，因此一个汉堡总数递减的顺序就是我们需要的。然后就是遇到汉堡总数相同，但是分配不同的情况，这种时候，我们需要对相同情况下的鸡肉汉堡排序，吃的总汉堡数越多...

思路： 题目的主要信息：  数轴上有n个点，每个点有自己的坐标和数值 从任意点出发，求经过K个不同数值点的最小花费  方法一：暴力法（超时）具体做法：对排序后的坐标点，每个点都可以作为一个区间的起点，我们遍历所有起点，往后遍历，找到后续区间是否有k个不同数值的点（使用哈希表，哈希表key值记录坐标上的数值，哈希表大小达到k即可），对于所有的区间，我们找到一个最小值即可。  class Solution { public: static bool comp(vector<int>& a, vector<int>& b){ //重载比较 return a[1...

思路： 题目的主要信息：  n个字符串，从第一个字符串开始作为左边个单词，依次遍历后面的作为右边单词 当左边单词的尾字符与右边单词的首字符相同是，消去这两个字符，消去之后继续比较，如此循环直到不同 将左边单词与右边单词首尾拼接作为下轮的左边单词，往后遍历 求遍历完最后剩余的字符串  方法一：直接比较+字符串截取具体做法：我们直接用a和b表示左右两个字符串，初始a为第0个字符串，b为第1个字符串，然后用下标比较二者的首尾，找到第一个不同的a字符串尾和b字符串首，然后用字符串截取函数substr截取a从头到不相同的第一位，b的不相同第一位到尾，将二者拼接作为新的字符串a，进入后续遍历。 class...