DAY 01 ~ DAY 02 —— 贪心算法
贪心算法的定义
贪心算法（Greedy Algorithm）是一种在每一步决策中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的解题策略。它不追求整体最优，而是通过一系列局部最优的选择，逐步构建最终解决方案，最终期望得到全局最优解。
贪心排序
在数据之间没有相互的联系时，可以通过对数组（或其他类型的变量，例如string类型）的排序来取得最优解。
这里顺便复习一下sort()排序。
普通数组：
其他类型（vector，string）：
例题
题目描述
在一个神秘的魔法王国里，两个强大的巫师，
吉娜 和 安度因，他们在打一起打副本的时候遇到了一个难题。
现在每个巫师手里都有一个装满魔法符文的袋子，这些符文由小写英文字母分别表示为字符串 s和 t。他们可以通过重新排列各自字符串中的字符来获得一个新的符文组合。
如果两位巫师可以在重新排列字符串 s和 t 后让 s的字典序 < t 的字典序输出YES，否则输出NO。
参考代码
这道题让我们求字符串 sss 和 ttt 重新排序后能否让 sss 的字典序小于 ttt 的字典序。
所以贪心思想就是将 sss 按字典序按最小的情况排序，将 ttt 按字典序最大的情况排序，如果这样都不行的话，那就说明 sss 的字典序绝对大于 ttt 的字典序。
贪心 - 优先队列
优先队列是什么？
优先队列是一种特殊队列，元素按优先级排序，出队时优先取出最高优先级元素，常用于调度、任务处理等场景，实现方式有堆、二叉搜索树等。
优先队列分为两种：升序与降序。
为什么要使用优先队列
请看这道题：
题目描述
在一个果园里，超级阿拉已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。超级阿拉决定把所有的果子合成一堆。
每一次合并，超级阿拉可以把两堆果子合并到一起（不一定是相邻的两堆果子），消耗的体力等于两堆果子的重量之和。可以看出，所有的果子合并到最后就只剩下一堆了。超级阿拉在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以超级阿拉在合并果子时要尽可能节省体力。你的任务是使超级阿拉消耗的体力最少，并输出这个最小的体力消耗值
数据范围：0<N<105+10<N<10^5+10<N<105+1 。
为什么这道题要用优先队列，问题就出在数据范围。
sort排序在此代码中时间复杂度为O(n² log n)，在n=105n=10^5n=105会TLE，然而优先队列能在O(1)时间获取到最小（最大）值，用O(log n)的时间完成插入和删除。
反悔贪心
请看题目：
题目链接
这道题第一反应是前面先用砖块搭上去，后面再用梯子。
但如果你先用了砖头，用完了后遇到了更小的差值，不就反悔了吗？
先用了梯子，用完了后又遇到了更大的差值，不就又反悔了吗？
这道题就是典型的反悔贪心。
前面我们先无脑用梯子，后面遇到差值比较此次差值与前面的差值的最小值用砖头填充就好了。
如果此时砖头不够了，那就说明无法到达更远的建筑，记录下当前坐标-1即可
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 03 —— 前缀和数组
前缀和数组的定义：
* 前缀和数组：对于数组 a ，其前缀和数组prefix 满足prefix[i] = a[0] + a[1] + ... + a[i]，即从数组起始位置到第 iii 个元素的累加和。
前缀和数组用于快速计算数组中某段连续元素的和，关注 "从开头到当前"。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前缀和数组的应用
题目描述
在一个遥远的科技王国里，有一位年轻的数学天才，名叫艾伦。艾伦非常擅长解决数学难题，并且从小就对数据结构和算法充满兴趣。某一天，王国的国王遇到了一道难题，他需要根据给定的数列和多个区间，快速计算每个区间内的元素和。
国王找到了艾伦，希望她能帮助解决这个问题。艾伦看着国王给出的数据和区间，发现这正是一道典型的区间和问题。
给定 nnn 个正整数组成的数列 a1,a2,a3…,ana_1, a_2, a_3 …,a_na1 ,a2 ,a3 …,an 和 mmm 个区间 [li,ri][l_i,r_i][li ,ri ] ，分别求 mmm 个区间之和。
参考代码
这道题用暴力的方法是可以的一部分分的，但是数据范围：1≤n,m≤1051≤n,m≤10^51≤n,m≤105
105∗105=101010^5 * 10^5=10^{10}105∗105=1010，会超时，所以要用前缀和数组。
前缀和数组的公式一定要记牢：pre[i]=pre[i-1]+a[i]。
推导过程
由于前缀和数组用于求和，所以：
* pre[i]表示原数组中从第 0 个元素到第 i 个元素的总和，即：
pre[i] = a[0] + a[1] + ... + a[i-1] + a[i]
* 而 pre[i-1] 表示从第 0 个元素到第 i-1 个元素的总和，即：
pre[i-1] = a[0] + a[1] + ... + a[i-1]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
将两式对比可见，pre[i] 比 pre[i-1] 多了一个a[i]，因此自然有：
pre[i] = pre[i-1] + a[i]
总结
这个公式是优化计算效率的关键 —— 它将重复累加的过程转化为单次加法，体现了「用空间换时间」的算法思想。
之前写空间换时间被 复仇者_某某 喷，这次就解释一下
用pre数组的空间换取O(n*n)的时间复杂度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
异或前缀和
什么是异或？
异或（XOR，Exclusive OR）是一种逻辑运算，也是计算机科学中常用的位运算，其运算规则可以概括为：两个操作数的对应位相同则结果为 0，不同则结果为 1。
多位数的异或运算
当对两个多位数（如整数）进行异或时，需按二进制位逐位运算，即对两个数的每个对应二进制位分别执行异或，最终组合成结果。
实例：5 ^ 3 = ?
5(10)=101(2),3(10)=011(2)5_{(10)}=101_{(2)},3_{(10)}=011_{(2)}5(10) =101(2) ,3(10) =011(2)
110(2)=6(10)110_{(2)}=6_{(10)}110(2) =6(10)
所以5 ^ 3 =6。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
其实说白了，
异或前缀和不能被当做一个新的知识点
它只是前缀和的变种而已
将前缀和数组的加号改成异或 ^ 就好了
所以异或前缀和的知识点不在前缀和，而在异或。
