搜索结果
查询Tags标签： mid，共有 942条记录-
搜索插入位置
搜索插入位置 一、题目描述 给定一个有序数组。需要插入一个元素。返回插入索引。 请必须使用时间复杂度为 O(log n) 的算法。 实例 输入: nums = [1,3,5,6], target = 5 输出: 2输入: nums = [1,3,5,6], target = 2 输出: 1输入: nums = [1,3,5,6], target = 7 输出: 4二…
2022/9/16 6:17:30 人评论 次浏览 -
排序算法整理C++（初赛）
排序算法整理 常见考点将一个乱掉的字符串排回有序（以交换为基本操作）的最少操作，就是冒泡排序。 排序算法的稳定性 排序算法的时间复杂度排序算法的稳定性 稳定性是指排序前两个元素a1 = a2，a1在前。排序过后，倘若a1始终在前，则算法是稳定的，否则是不稳定的。 稳定…
2022/9/5 1:26:10 人评论 次浏览 -
二分法查找
1.需求： 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 2.示例: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 3.提示： 你…
2022/9/3 23:25:12 人评论 次浏览 -
cdq分治
cdq分治，一种广为人知的离线分治算法。大体的思想是：将左右两边区间分开递归处理。 统计左边区间修改对右边区间查询的影响。第一步很简单，写两个递归就行了。关键在第二步。我们搞个cdq的经典问题——三维偏序来具体解释这个东西。 P3810 【模板】三维偏序（陌上花开）…
2022/9/3 23:22:59 人评论 次浏览 -
793. 阶乘函数后 K 个零
labuladong 题解思路 难度困难187收藏分享切换为英文接收动态反馈 f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。给定 k，找出返回能满…
2022/9/2 23:25:08 人评论 次浏览 -
CF431E Chemistry Experiment
CF431E Chemistry Experiment 题目大意 有\(n\)支试管，每支试管装有\(h_i\ ml\)的水银。 \(q\)次操作，操作有两种：1 \(p\) \(x\)：倒掉试管\(p\)的水银修改为\(x\ ml\)。 2 \(v\)：将\(v\ ml\)水任意分配至\(n\)支试管里，最小化有水的试管中最大体积，输出这个最小值，…
2022/8/30 23:23:01 人评论 次浏览 -
快速排序
快速排序 快速排序是一种分治的递归算法，平均时间复杂度：O(NlogN)。 1.1 基础版 //递归方法 int parition(vector<int> &arry, int left, int right) {int pivotkey; //枢轴值pivotkey = arry[left];while (left < right) {while (pivotkey<= arry[righ…
2022/8/29 23:25:54 人评论 次浏览 -
搜索旋转排序数组
目录题目描述解题思路解题代码 题目描述题目地址：https://leetcode.cn/problems/search-in-rotated-sorted-array/ 题目要求 整数数组 nums 按升序排列，数组中的值互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转…
2022/8/28 23:28:07 人评论 次浏览 -
LeetCode/阶乘后的零
1. 返回尾零数量 可以转换为求质因子为2和5数量的较小值，实际上就是求质因子为5的数量 class Solution { public:int trailingZeroes(int n) {int ans = 0;for (int i = 5; i <= n; i += 5) //遍历所有含质因子5的数for (int x = i; x % 5 == 0; x /= 5) //计算该数有…
2022/8/28 6:23:51 人评论 次浏览 -
P2680 [NOIP2015 提高组] 运输计划 【二分+LCA+树上差分】
题目描述 公元 \(2044\) 年，人类进入了宇宙纪元。 L 国有 \(n\) 个星球，还有 \(n-1\) 条双向航道，每条航道建立在两个星球之间，这 \(n-1\) 条航道连通了 L 国的所有星球。 小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 \…
2022/8/27 6:24:35 人评论 次浏览 -
AT2580 题解
前言 题目传送门！ 更好的阅读体验？ 这题是常规的二分答案。 前置知识：二分答案 教大家一个小技巧：如何判断一题是否可以使用二分答案，以及如何编写程序？设计 \(f(x)\) 函数，确认其是否满足单调性。 如果不满足单调性，可能是 \(f(x)\) 函数设计错了，但更有可能是本…
2022/8/26 6:24:51 人评论 次浏览 -
SP733 题解
前言 题目传送门！ 更好的阅读体验？ 校内比赛题。赶紧补篇题解。 思路 经典的二分加搜索。 由于 \(h_{i, j}\) 范围很小，考虑二分答案。 二分答案的范围应该是 \([0, 110]\)。 对于 \(\texttt{check()}\) 函数，可以暴力枚举所有差为 \(\texttt{mid}\) 的数对，并使用 b…
2022/8/26 6:23:39 人评论 次浏览 -
AT1330 题解
前言 题目传送门！ 更好的阅读体验？ 这一题内部比赛时考到了，个人觉得是一道二分答案好题。 本题时间很宽松，导致 \(O(n \log^2 n)\) 的代码可以跑过去。 但是，我内部比赛的时限是 \(1\) 秒，这就导致需要 \(O(n \log n)\) 的代码了。 思路一 显然是一道二分答案题目。…
2022/8/26 6:23:35 人评论 次浏览 -
01分数规划
01分数规划 经典例题：POJ2976 给定 \(n\) 个物品的价值 \(a\) 和 花费 \(b\) ，取其中的 \(k\) 个物品，求 \(\sum a[i] / \sum b[i]\) 的最大值。 题解： 假设 \(\sum a[i] / \sum b[i] = x\) ,则： 当 \(x\) 不是最优解时，\(\sum a[i] / \sum b[i] \ge x\) 成立，则存…
2022/8/24 6:53:08 人评论 次浏览 -
AcWing算法基础课---第一讲基础算法---01排序
快速排序 步骤确定分界点：q[l], q[(l+r)/2], q[r], 随机 调整区间 递归处理void quick_sort(int q[], int l, int r) {if (l >= r) return; //递归结束条件int i = l - 1, j = r + 1, x = q[l + r >> 1]; //定义i, j指针, 确定分界点x（一般取中间值）while (i …
2022/8/23 1:55:12 人评论 次浏览
