我遇到了这个问题：
一个鞋匠有N份工作（顾客的订单）要做。
鞋匠每天只能做一份工作。每项工作我，T[I]
（1≤t[i]≤1000）是鞋匠完成
工作。在开始工作前每延迟一天，
鞋匠必须支付S[i]分（1≤S[i]≤10000）的罚款你的任务是
帮助鞋匠找到总数最少的工作序列
好的。
解决方案简单地说：
按S[I]/T[I]排序。不要用浮子！
有人能详细说明一下解决办法吗？我知道我们必须先做低t和高s的工作，我知道对于一些输入，这是如何工作的，但是有人能证明，按s[i]/t[i]排序在一般情况下是有效的吗？
最佳答案
证据是这样的：假设工作的顺序是固定的。让我们看看两个相邻的作业。如果我们交换它们，这两个之前和之后的工作的答案不会改变所以我们可以忽略所有其他的工作，看看如果我们交换这两个工作，就好像没有其他工作一样。如果没有交换，罚款是f1 = s1 * t1 + (t1 + t2) * s2。如果它们被交换，则为f2 = s2 * t2 + s1 * (t1 + t2)。在最佳答案中，这意味着f1 <= f2或s2 * t1 <= s1 * t2。这个比较器是可传递的，所以一个最优的局部排序给出了一个最优的全局答案。