额。。某不正经的我又来了，被二分答案恶心到了之后，我又开始搞贪心了，并且发现贪心也不是什么友好的东西。。。（甚至比二分还恶心）
额，先来说说从网上一个课件上找到的一道好题吧。。。
题目是这样的：一些人在排队等待一项服务（你可以把它理解成银行办理业务之类的），每个人有他们的办理业务的时间ti，排在后面的人就必须等。现在让你安排排队次序，使总的等待时间最小。
这很显然是个贪心，并且按照一定的规则排序。我相信聪明的同学都已经想出来了，正解是按时间从小到大排序，然而我太弱了，没想出来怎么排序，于是就证明了一番。。。
证明如下：
我们不妨分析两个人的情况。
如图所示，a,b两个人的服务时间分别是ta,tb，排在a,b之前的所有人的总服务时间为T，总等待时间为W，则，
我们设决策1优于决策2，即总等待时间W1<W2。根据图示，我们知道a,b无论谁排在前，谁排在后，a,b之前的人的排队次序已经决定了（因为我们的研究对象只有a,b），即T与W都是定值，所以对于决策1，等待时间wa=T,wb=T+ta。对于决策2,等待时间wb=T,wa=T+tb。因此，总等待时间W1=W+2*T+ta，W2=W+2*T+tb。又因为W1<W2.。所以W+2*T+ta<W+2*T+tb。移项得：ta<tb，又因为决策1更优（即a排在b前面时更优）,所以等待时间ti越小的排在前面越优。因此我们得出结论：当队列按等待时间从小到大排时，答案最优。
好严（gui）谨（chu）的证明啊！我第一眼看有点不懂，但理解了之后就很容易了qaq。
貌似这证明的实质用到了排序不等式？不懂，跪求数学奥赛dalao解答。
好像NOIP2012的国王游戏也可以这么证？呵呵，考场上这么证绝对要崩溃的。。