【题解】
1、字符涂改

依次次扫描每个字符，对于字符i：

如果S[i]==T[i]，则继续扫描下一个字符；

如果S[i]!=T[i]，则从这个字符开始涂改，涂改的长度为从i开始，直到遇到相同字符为止(或字符串结束)。

时间复杂度O(n)

2、雇佣兵

二次贪心：最优子集 + 最优指派

首先按雇佣金有小到大把雇佣兵排序，按次顺序依次考虑每个雇佣兵；

对雇佣兵i，指派能被他消灭的魔鬼中魔力值最大的。可以用set优化。

时间复杂度O(nlogm)

3、食堂餐位

二分答案+贪心验证+优先队列优化

二分猜m的值，范围为[1,n]。

对于猜的mid，用贪心验证：计算在餐位数为mid时，n个学生用餐总时长的最小值，若这个不大于tot，则说明mid合适，下次继续在左半边猜（因为求最小的m），否则继续在右半边猜。

贪心验证：设置小顶队维护每个同学用完餐的时间。先把t[1]..t[mid]进入小顶队，接着取出栈顶x=q.top()，并删除栈顶（该同学最早用完餐），接着把 x+t[mid+1] 进队列（m+1 号同学用晚餐的时间是x+t[m+1]），然后考虑m+2,m+3，...，重复上述队列操作。最后用完餐的同学就是用餐总时长。

时间复杂度(n*logn*logn)

4、身高推算

DAG图的最长路径

建图：把每个同学看成图的一个顶点；

首先从点k向其他点引一条有向边，边权为0，认为其他人不比k高。

然后对于每条信息a,b，先从b引一条有向边到a，边权为0（a不比b高），再从a向 a,b之间的点分别引一条有向边，边权为 -1。

然后跑拓扑排序算法：先令入度为0的点的h[i]=hmax，然后BFS过程中得到每个点的边权和的最长路径长度。

时间复杂度O(n+e)，e表示边的数目