TheJediTest

作者：谢兴宇 徐明宽

关键词：搜索 贪心

题目简述

一座有n层的楼上有一些学生，第$i(0\le i<n)$层有$students_i$个学生。你被给定了一个数k，如果第i层有x个学生，那么这一层需要$\lceil {x \over k} \rceil$个老师。你可以调整每个学生的楼层，但是每个学生至多只能调整一层，就是说第i层的学生只能去第i-1层（如果有的话）、第i层、第i+1层（如果i+1<n)。现在你希望请最少的老师教你的学生，请求出这个最小值。

$1\le n\le 20,1\le students_i,k\le 10^8$

分析

换一个角度，就是要最小化所有老师教不满的学生数量的和。

即如果最终的第i层有$b_i$人，就是要最小化$\sum_{i=1}^n(k\lceil{b_i\over k}\rceil-b_i)=\sum_{i=1}^n(k-(k\ mod \ b_i))$。

算法一

本着暴力至上的原则。。这么小的n不写个暴搜实在是对不起出题人啊。

我们从小往大考虑每一个楼层与下一个楼层之间的学生调整，假设当前在考虑第i层与第i+1层，显然我们只需要考虑净调整（就是说如果从第i层有若干个学生调整到i+1层，又有若干个学生从第i+1层调整到第i层，这当然没有意义）。假设第i层当前有$b_i$个学生，其中$a_i$个是本来就在这里的，那么考虑从第i层调整到第i+1层的学生数量，必然是$min(b_i \ mod \ k,a_i)$，从第i+1层调整到第i层的数量必然是$min(k-(b_i \ mod \ k),a_{i+1})$，因为如果能把当前层调整成k的倍数的话，那必然比让它不是k的倍数要优。

算法二

其实我们没有必要搜索。。

还是从小往大考虑楼层之间的调整，假设第i层不能把人调整到第i-1层。如果说$a_i \ge b_i \ mod \ k>0$，那么我们直接把$b_i \ mod \ k$扔到下一层；否则的话，我们就从下一层抽一些来尽可能补足$b_i-(b_i \ mod \ k)$；这样显然是最优的。这样的话当我们再考虑第i+1层，会发现要么第i+1层已经没有人了，要么第i层已经是k的倍数；第i+1层不可能再把人扔到第i层了，所以我们可以继续递归地考虑第i+1层。

算法三

我们不妨这样考虑：一个有序的数列，有$students_i$个i，你要把它们分成若干份，使得每一份都是一段连续的区间，满足每个区间中数的个数不超过k，且其最大值和最小值的差值不超过2；在此基础上要使份数最少。

那么这就是一个经典的贪心问题了~

从小往大能选就选即可。具体来说的话，就是从小往大考虑，如果第i层还剩x（模k以后）个人，那么就先从第i+1层、再从第i+2层找尽量多的人凑出k来删掉就可以了。