磊落

Thinking will not overcome fear but action will.

排队打谁

排队打水 贪心问题的一般证明的两种方法 反证法 数学归纳法 ans >= cnt, cnt >= ans => ans == cnt 有 n 个人打水，每个人打水时间为t(i), 求如何排列打水顺序，让总的等待时间最短。 思路 - 让最墨迹的人排在最后 - 让打水时间最快的排在最前边 #include...

Posted by 磊落 on May 11, 2020

快速排序

快速排序 特点 不稳定排序算法 平均复杂度O(nlog2(n)), 最坏时间复杂度O(n^2) 快排思想–分支思想（不稳定算法） 确定分界点：区间左端点，区间右端点，区间中点，随机选点。 （四选一） 调整区间： 让小于等于分界点的值在分界点的左边，让大于等于分界点的值在分界点右边 递归...

Posted by 磊落 on May 11, 2020

归并排序_逆序对

逆序对 思想 5 4 3 2 1 逆序对是一个数字和后边每一个比它小的数字都构成一个逆序对 在归并过程中分为三类 两个数字在区间左边求逆序对：直接返回merge_sort() 两个数字在区间右边求逆序对: 直接返回merge_sort() 两个数字在区间两边求逆序对: 在归并过程中，右边数组中每加入一个数，...

Posted by 磊落 on May 11, 2020

归并排序

归并排序 特点 稳定排序 时间复杂度：O(nlog2(n)) 递归log2(n)层，每层时间复杂度为O(n) 思想 确定分界点，将给定序列中点作为分界点，划分成两个子序列 mid = (l + r) / 2 递归排序左右区间 left 和 right 归并两个有序数组，注意是有序数组，...

Posted by 磊落 on May 11, 2020

差分

差分 思想 一维差分 一直a1, a2, …, an. 构造b1, b2, …, bn 使得 ai = b1 + b2 + … + bi b数组称为a数组的差分，a成为b的前缀和。 一维差分的用处：假设想对a[L~R]中每个数都加上一个常数C. 即 a[L] + C, a[L+1] + ...

Posted by 磊落 on May 11, 2020

合并果子

合并果子 每次合并权值最小的两个点，要求最后总体体力值最小。 证明 权值最小的两个点，深度最深，且可以互为兄弟。 证明n - 1 个点合并的最小值一定满足 n 个点合并的最小值。 证明 F(n) = F(n - 1) + (a + b) 其中 (a + b) 又是最小的两个点，证毕。 #includ...

Posted by 磊落 on May 11, 2020

双指针算法

双指针算法 思想 双指针算法都是把暴力算法写出来，然后看有没有单调性，如果有单调性就可以把时间复杂度降低 两个指针移动将O(n ^ 2)的算法优化成O(n) 特点 *模板 ``` for (int i = 0; i < n; i++) while (i < j && check(i, j)) j ++; ``` /...

Posted by 磊落 on May 11, 2020

区间覆盖

区间覆盖 将所有区间按照左端点从小到大排序 从前往后依次枚举每个区间，在所有能覆盖start区间中，选择右端点最大的区间 将Start更新成右端点最大值 证明 ans 代表所有可行方案的最小值 cnt代表按照上述方案选法的某一个可行解 所以 ans <= cnt 证明 ans >= ...

Posted by 磊落 on May 11, 2020

区间合并

区间合并 算法例题描述 给定 n 个区间 [li,ri]，要求合并所有有交集的区间。 注意如果在端点处相交，也算有交集。 输出合并完成后的区间个数。 例如：[1,3]和[2,6]可以合并为一个区间[1,6]。 输入格式 第一行包含整数n。 接下来n行，每行包含两个整数 l 和 r。 输出格式 共一行，包含...

Posted by 磊落 on May 11, 2020

前缀和

前缀和 思想 原数组 a1, a2, a3, a4, a5, …, an 前缀和 Si = a1 + a2 + a3 + … + ai (i = 1~n) 一维特点 规定：S0 = 0，所有待求数组下标都是从1开始 Si = Si-1 + ai 求[l, r]区间内所有值之和 sum ...

Posted by 磊落 on May 11, 2020

FEATURED TAGS
ABOUT ME

Who am I? Where am I from?

✉️ csuperlei@gmail.com