team2012-D1-sol-0039

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

很厉害的一道题... 看了这道题就想到要二分, 但是关键是在 check() 函数怎么写, 线性贪心显然是不行的, 每种贪心都可以很容易地举出反例, 这里就不提了. 于是想到dp, 用 f[i] 表示"前 i 个人分完组后最小的 Rsum", Rsum = R1 + R2 + ... + Rm (假设前 i 个人分为 m 组的情况下). 转移方程是
{{{
f[i] = min{ f[j]+max{rp[k]|j+1<=k<=i} | sum{gf[k]|j+1<=k<=i} <= Gmax };
}}}
其中 Gmax 是 check（） 传进来参数， 表示每一组的 Gi 的上限是多少.

因为是求一个区间的最值, 所以我一开始就想写线段树来搞, 但是后来发现简单的记录一两个值似乎没办法搞. 于是去问了学姐之后知道了可以用单调队列 + set 来找最值. 这道题可以单调队列优化的最关键一点在于每个元素出队要修改的信息只需要 O(1) 的时间. 这一点我刚开始一直没想清楚. 关于单调队列维护什么, 待我之后组织好文字再补上.

很厉害的一道题... 看了这道题就想到要二分, 但是关键是在 check() 函数怎么写, 线性贪心显然是不行的, 每种贪心都可以很容易地举出反例, 这里就不提了. 于是想到dp, 用 f[i] 表示"前 i 个人分完组后最小的 Rsum", Rsum = R1 + R2 + ... + Rm (假设前 i 个人分为 m 组的情况下). 转移方程是

f[i] = min{ f[j]+max{rp[k]|j+1<=k<=i} | sum{gf[k]|j+1<=k<=i} <= Gmax };

其中 Gmax 是 check（） 传进来参数， 表示每一组的 Gi 的上限是多少.

因为是求一个区间的最值, 所以我一开始就想写线段树来搞, 但是后来发现简单的记录一两个值似乎没办法搞. 于是去问了学姐之后知道了可以用单调队列 + set 来找最值. 这道题可以单调队列优化的最关键一点在于每个元素出队要修改的信息只需要 O(1) 的时间. 这一点我刚开始一直没想清楚. 关于单调队列维护什么, 待我之后组织好文字再补上.