个人思路:
从小到大排序,因为一定先满足小的,再满足大的。
分组时,我们发现,同一组内的数在排序后的序列内连续,这样更优。因为(不会证)。
我们预处理出对于每个出书数量的答案,查询时直接输出即可。我们发现出书数量越多,满足人数越少,但是不能递推。
如果求出满足前 \(i\) 个时的最多出书数量 \(t_i\),我们就可以反推答案。但是也不能递推。
状态:\(dp_i\) 表示满足前 \(i\) 个时,前 \(i\) 个数最多分为多少组。
转移:
当 \(i < a_i\) 时,显然不能满足。此时 \(dp_i = 0\)。
否则,\(dp_i = \max\limits_{1\le j<i-a_i} dp_j + 1\),我们只需要划分至少 \(a_i\) 个数与 \(i\) 一组,剩下的数尽量多分。
答案:
对于 \(i < a_i\) 时,满足前 \(i\) 个时的最大出书数量 \(t_i\) 即为 \(n - a_i + 1\),即前 \(a_i\) 个分一组,剩余一个一组。
否则,满足前 \(i\) 个时的最大出书数量 \(t_i\) 即为 \(dp_i + n - i\),即前 \(i\) 个分 \(dp_i\) 组,剩余一个一组。
显然,对于 \(i < a_i\) 时,这个答案不一定最优,因为可以和后面的分成一组。于是,我们从右往左遍历,\(t_i \leftarrow \max(t_i, t_{i+1})\)。
反推答案,对于 \(t_{i+1} < p \le t_i\),\(ans_p = i\)。
然后稀里糊涂地过去了。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章