HDU 6709 – Fishing Master

题目链接：HDU 6709

考虑什么情况下花费的时间最少。我们要花的必要的时间是$k + \sum t_i$，如果所有的捕鱼工作全部能在煮鱼的时候完成。如下图所示：

这种情况花费的时间肯定是最小的，为$k + \sum t_i$，但是前提是$1 + \sum \lfloor \frac{t_i}{k}  \rfloor\geq n $。但是如果$t_i$很小，那么我们可能会牺牲$k – (t_i \bmod k)$的时间用来抓鱼，例如这种情况：

于是在$1 + \sum \lfloor \frac{t_i}{k}  \rfloor < n $的情况下我们可以牺牲前$n – (1 + \sum \lfloor \frac{t_i}{k}  \rfloor ) $个最小的$k – (t_i \bmod k)$来捉鱼，这样保证牺牲的时间是最小的。
其实我们可以观察到每一次开始煮鱼的时候也是捕新鱼的开始，我们其实只要对每一个这样的单位区间，这样的区间有三种情况，一种是出现捕鱼的时候不能煮鱼（即不等），一种是煮鱼的时候不能捕鱼（即等），一种是$t_i \bmod k = 0$。如果我们把煮鱼的时间看成是必要的，那么我们就要减少因为捕鱼浪费的煮鱼时间；如果我们把捕鱼的时间看作是必要的，那么我们就要减少因为煮鱼浪费的捕鱼的时间，这里也用到了定一个求另一个的思想。