算法考试总结
作者：lowlyli
时间：2021-12-8
内容：含泪写下这个算法的总结，太离谱了，我真的写不完，不会写。
问题回忆
算法复杂度
这题其实很简单，但比以往的上课题一点点复杂
大意：
主定理盒递推都可以
流水作业调度（变形）
基本步骤一样，就是这个卷子给的数字和计算规模大，写不完。
问题描述 n个作业要在两台机器M1和M2上进行加工。每个作业加工的顺序都是先在M1上加工，然后在M2加工。M1和M2加工作业$i$所需的时间分别为$a_i$ 和$b_i$。确定n个作业的最优加工顺序，使得加工完成所需的时间最少。
算法
- 分为$N_1,N_2$集合存放
- $N_1$中作业按照$a_i$升序排序，$N_2$中作业按照$b_i$降序排序
- $N_1$连接$N_2$，计算时间
哈夫曼编码
简单送分题（送命题）
这题和平时步骤一样，唯一区别就说这个题是10个字母的，上课也只有6，7个的，10个的规模有点大，写了满满一面的步骤和树，画吐了。
暖气管道最优安排
这题很迷惑，给了22个点,每个点包括$(x_i,y_i)$,问有没有最佳的一个点$(0,y_{best})$,这题没见过，考试跳过了，其实就说二分法求中位数
类似：
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。
如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？
给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。
（这15分基本上空了，没时间写，后面想到了，二分中位数，但22个数，每日吐槽题量大）
活动安排
这里是等待，有n个顾客，每个人需要$t_i$的服务时间，有m个窗口，求最短的等待时间的安排
就是贪心，从小到大排序，依次插入窗口。
（再次吐槽，给了10个数，2窗口，没时间写）
最长递增子序列
离谱，如果考实践的时候我还会（其实现在也会写代码）但这里理论分析，属实蚌埠住了，最离谱的是2种方法，放过我吧，我只写了后面的问题求解，理论属实不会。
这是考场上想到的：居然蒙对了一个，不过第二种属实不会了。
这里自己参考：
力扣最长递增子序列
回溯法和分支限界
这里是0-1背包变形
但这里要求2次，还是5层的树。
最后就一点点时间了，稀里糊涂画的，现在想起来，答案估计都有问题。唉~题量也太大了。根本写不完。
反思总结（也给一点准备建议）
总结
这次考试，题量大的离谱，我这种写的慢的，当年数据库都没写完的人，这根本写不完，除非，我不用思考，但这题还是有点难度，需要思考的，不清楚为啥19如此难。本来2周前就考了，因为突如其来的疫情，推迟了，导致理论和实践间隔久，反正就是只复习了书上，然后老师画的重点，然后就崩了。呜呜呜。
备考建议:
课上内容不太行，建议在平时学习看一遍书就可以开始刷力扣了，培养题感，这里推荐：
代码随想录 : https://www.programmercarl.com/
可以参考上面的最基础的地方刷，本人在2周多一点刷了100来道，虽然考试帮助不太大，但感觉还是学到了算法的一些精髓。
理论的一些可以参考：胡神的博客
还是可以的，我的一般吧。
没有什么了，算法好好学吧。
老师总结
最后也算4人之一，考的不是很差，但算法学习感觉还是很重要，尤其我这种没有参与过acm的人，有时间再多学一下吧，讨厌机试。
