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$。如果我们把煮鱼的时间看成是必要的,那么我们就要减少因为捕鱼浪费的煮鱼时间;如果我们把捕鱼的时间看作是必要的,那么我们就要减少因为煮鱼浪费的捕鱼的时间,这里也用到了定一个求另一个的思想。

 

 

说点什么

avatar
50
  Subscribe  
提醒