蓝桥杯 - 分果果

Jelefy · 2023-03-15 16:33:55 · 题解

题目描述

小蓝要在自己的生日宴会上将 n 包糖果分给 m 个小朋友。每包糖果都要分出去，每个小朋友至少要分一包，也可以分多包。

小蓝已经提前将糖果准备好了，为了在宴会当天能把糖果分得更平均一些，小蓝要先计算好分配方案。 小蓝将糖果从 1 到 n 编号，第 i 包糖果重 w_i。小朋友从 1 到 m 编号。每个小朋友只能分到编号连续的糖果。小蓝想了很久没想出合适的分配方案使得每个小朋友分到的糖果差不多重。因此需要你帮他一起想办法。为了更好的分配糖果，他可以再买一些糖果，让某一些编号的糖果有两份。当某个编号的糖果有两份时，一个小朋友最多只能分其中的一份。

请找一个方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，请输出这个差。

评测用例规模与约定

对于所有评测用例，1 \leq n \leq 100，1 \leq m \leq 50，1 \leq w_i \leq 100。在评测数据中，w_i 随机生成，在某个区间均匀分布。

题解

考虑 DP。

大概可以列出这五个维度：分出的区间个数，最后一个用了一颗糖的位置，最后一个用了两颗糖的位置，区间和的最小值，区间和的最大值。

考虑把其中一维拿出来作为 DP 维护的值，这一维必须满足的条件是满足越大越优或者越小越优的单调性。

只有最小值和最大值满足单调性。此时很关键的一点，我们发现最小值有上界 \frac {2\cdot sum}{m}，使得时间复杂度有显著的优化，而最小值有一个不太重要的下界，因此我们枚举最小值，把最大值作为 DP 维护的值。

设计 DP 转移

令 sum=\sum w_i，规划 DP：f_{i,j,k} 表示前 i 个区间，最后一个用了一颗糖的位置在 j，最后一个用了两颗糖的位置在 k（在 k 之前也行），最大值最小是多少。考虑 3 种转移：

• f_{i,j,k}\leftarrow f_{i,j,k-1}

• 第 i 个人用了上一次的 j+1 开始的一段，这种转移是 f_{i,j,k}\leftarrow \max(f_{i-1,j',k},s_j-s_{j'})

• 第 i 个人用了上一次的 k+1 开始的一段，这种转移有两类：

  • 然而这种转移（区间互相包含）一定不优。
  • f_{i,j,k}\leftarrow \max_{}(f_{i-1,k,j'},s_k-s_{j'})$，要求是 $j'\le k\le j

    转移是 O(n) 的，注意转移合法的要求是新的一段和 \ge mi

    区间包含不优证明

    为什么区间互相包含一定不优？我们可以从调整的角度来想这个问题。首先构思一个大区间，一个小区间，还有一个区间位于小区间的右边，但与大区间存在一部分重叠，称这个区间为右区间。

第一个结论：小区间和右区间之间不应该存在间隔。很显然小区间右端点调整到右区间的左边会更优。

而当小区间和右区间之间没有间隔后，我们就可以把大区间的右端点调整为小区间的右端点，显然这样大区间的和会更接近于小区间的和，使得结果更优。

如果没有右区间，同理我们可以将小区间的右端点调整到大区间的右端点。

考虑这样做的复杂度，实际上是 O(\frac {2\cdot sum}{m}×n^3m)=O(sum\cdot n^3)。

优化

• 对于第三类转移，不难发现 f_{i,j,k} 是随着 k 增加而单减的，那么选取尽量靠后的转移点一定最优。

• 对于第二类转移，考虑单调栈优化。具体地说，由于 s_j-s_{j'} 是随 j' 增加而单调递减的，我们需要的是 min\{s_j-s_{j'},f_{i-1,j',k}\} 最小，那么当 s_j-s_{j'} 变大时，若 f_{i-1,j',k} 也变大，那么这样的点 j' 可以舍弃，符合单调栈的原则。而我们发现，随着 j 的增加，s_j-s_{j'} 的图像是向上平移的，这将会导致最佳转移点的右移；而 f 的图像只能被“往下压”，在其长度不变短的情况下，也会导致最佳转移点的右移。因此我们维护这个最佳转移点即可，值得注意的是最佳转移点可能是相邻的两点。

  Code

有点卡时，在洛谷上开 O_2 才能过。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 51, N = 101;

int n, m, w[N], f[M][N][N], st[N], ans = 0x7fffffff;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &w[i]);
        w[i] += w[i - 1];
    }
    for(int minw = 1; minw <= 2 * w[n] / m; minw++){
        memset(f, 0x7f, sizeof(f));
        f[0][0][0] = minw;
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++){
                *st = 0;
                int p = 0, pst = 1;
                for(int k = j; k <= n; k++){
                    if(j > 0) f[i][j][k] = f[i][j - 1][k];
                    while(w[k] - w[p] >= minw){
                        if(p >= j){
                            while(*st && f[i - 1][j][p] <= f[i - 1][j][st[*st]])
                                (*st)--;
                            st[++*st] = p;
                        }
                        p++;
                    }
                    if(*st){
                        pst = min(pst, *st);
                        while(pst < *st && f[i - 1][j][st[pst + 1]] < w[k] - w[st[pst + 1]])
                            pst++;
                        while(pst > 1 && f[i - 1][j][st[pst]] > w[k] - w[st[pst]])
                            pst--;
                        f[i][j][k] = min(f[i][j][k], max(f[i - 1][j][st[pst]], w[k] - w[st[pst]]));
                        if(pst < *st)
                            f[i][j][k] = min(f[i][j][k], max(f[i - 1][j][st[pst + 1]], w[k] - w[st[pst + 1]]));
                    }
                    int pp = min(p - 1, j);
                    if(pp >= 0)
                        f[i][j][k] = min(f[i][j][k], max(f[i - 1][pp][j], w[k] - w[pp]));
                }
            }
        }
        ans = min(ans, f[m][n][n] - minw);
    }
    printf("%d", ans);
    return 0;
}