hyf

    虽然USACO已刷完，但最近遇到一些相似问题依然频频出错，故在此记下一些笔记。

09-09-13
    usaco4.2有一道工件安排的题，大概题意是n个工件需要进行处理，必须先进行操作A然后是操作B，有m1台A机器和m2台B机器，给出每台机器的操作时间，要求最先完成所有工件操作A的时间和最先完成所有操作的时间。
    问题1的解法是很明显的贪心，即每次选出能最快完成当前工件的机器，证明很简单，从i-1到i选择最优机器是明显的，只需说明最优的i-1的局面对i是可以得出i的最优答案的，如果i-1有非最优局面添加一个工件可以达到更优，那么添加新工件的位置会占去一个以前的最优解位置，而以前的工件就会放到对于当时并不最优的位置上去，不会比把现在工件放到此位置更优。
    问题2的解法是按问题1的方法求出一个工件完成时间序列，然后用A大的匹配B小的这样的顺序来匹配，找出一个最大值就是答案。这个问题证明的关键是这样匹配的解是否是合法的（如果是合法的那么正确性显然），我们可以把工件的操作看成是倒着的，即先操作B再操作A,那么把操作B的部分换成B的最优操作序列显然是合法的，因为这是A和B的操作都是合法且不会互相干扰，并且必定不会比以前的差（因为这分别是A和B的最优操作序列），那么答案就是这两个序列的最有配对，显然最大配最小这样的顺序可得到最优解。