「Cookies」 饼干

GitHub跳转原题关系图返回列表

先按贪婪度降序排序证明最优分配单调，再用 f[i][j] 的两种转移（全体减 1 块 / 末尾一段各 1 块）做 O(n²m) DP 并回推方案。

OJ: roj

题目 ID: 3140

难度:提高+/省选-

标签:动态规划线性DP贪心输出方案

创建: 2026-10-01 20:12

更新: 2026-10-10 11:30

目录

  1. 形式化题目
    1. 样例解释
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定 nn 个孩子与 MM 块饼干，第 ii 个孩子的贪婪度为 gig_i。要给每个孩子分配正整数块数 c1,…,cnc_1,\dots,c_n，使 ∑ci=M\sum c_i = M，并最小化怨气总和

∑i=1ngi⋅#{ j:cj>ci }\sum_{i=1}^{n} g_i \cdot \#\{\, j : c_j > c_i \,\}

每个孩子的怨气等于「分到的饼干严格比自己多的人数」乘以自己的贪婪度。要求输出最小怨气值与任意一组达到该值的分配。

样例解释

样例 3 20 / 1 2 3 的最小怨气是 22。先核对一组最优分配 2 9 9（就是题面给出的那组）：

孩子 贪婪度 gig_i 饼干数 cic_i 比自己多的人数 aia_i 怨气 giaig_i a_i
1 1 2 2 2
2 2 9 0 0
3 3 9 0 0

第 1 个孩子拿得最少，两个孩子都比它多，所以 a1=2a_1 = 2，怨气 1×2=21 \times 2 = 2；后两人并列最多，各自的 aa 都是 00。合计 22，达到最小值。

所有最优分配（按贪婪度降序排列后）恰好是三组：(7,7,6)(7,7,6)、(8,8,4)(8,8,4)、(9,9,2)(9,9,2)。可以看到贪婪度最大的位置拿得不少于贪婪度小的位置，代价全部由贪婪度最小的人承担——这正是下面贪心排序的依据。本题解输出 (7,7,6)(7,7,6)，换回输入顺序即 6 7 7，同样合法。

正解

思路

第一步：先决定「谁多谁少」，再填数字。 直接枚举每个孩子的块数是 (M−1n−1)\binom{M-1}{n-1} 级的组合数，M⩽5000M \leqslant 5000 时完全不可行。但注意怨气只依赖块数之间的大小关系，与具体数值无关。于是可以交换论证：若 gi>gjg_i > g_j 却 ci<cjc_i < c_j，把两人的块数对调，只有这两人的项改变，而

giaj+gjai  ⩽  giai+gjaj  ⟺  (gi−gj)(aj−ai)⩽0g_i a_j + g_j a_i \;\leqslant\; g_i a_i + g_j a_j \iff (g_i - g_j)(a_j - a_i) \leqslant 0

对调后 ai,aja_i, a_j 互换；由于 gi⩾gjg_i \geqslant g_j 且对调前 ci<cjc_i < c_j 意味着 ai⩾aja_i \geqslant a_j，不等式成立。因此最优解中贪婪度越大的人饼干数越多。把 gg 降序排序后，只需构造非增序列 c1⩾c2⩾⋯⩾cnc_1 \geqslant c_2 \geqslant \dots \geqslant c_n，具体数值留到最后回填。

贪婪度并列的人之间顺序可任选。参考数据由某个具体实现（非稳定排序）生成，本题解的代码复刻了该实现在并列时的次序，从而与给定数据逐字节一致；这只影响「输出哪个最优方案」，不影响最小值与复杂度，下文只讨论算法本身。

第二步：从「前 ii 人」划分子集。 有了单调性，序关系就变成「前面的人拿得不少于后面」。设 fi,jf_{i,j} 表示降序后的前 ii 个孩子共分到 jj 块饼干时的最小怨气。要写出转移，只看第 ii 个人拿几块是不够的（它会同时影响自己和前面所有人的 aa 值），关键是改为对**「末尾有多少人恰好拿 1 块」**分类：

  • 情况 A：ci⩾2c_i \geqslant 2（最后一个人也不止一块）。 把前 ii 个人每人减 1 块。块数之间的大小关系完全没变，每个人的 aa 也没变，所以怨气不变；总块数从 jj 变成 j−ij-i。于是
fi,j=fi, j−if_{i,j} = f_{i,\,j-i}

这条转移说明：只要末尾还有余量，就可以把「多出来的层」一层层剥掉，剩下的只是核心问题。

  • 情况 B：ci=1c_i = 1（末尾一段人有且仅有 1 块）。 设断点 kk 使得 ck+1=⋯=ci=1c_{k+1} = \dots = c_i = 1 且 ck⩾2c_k \geqslant 2（k=0k = 0 表示前 ii 人全拿 1 块）。这一段每人上方恰有 kk 个人的饼干比自己多，所以每人贡献 k⋅gtk \cdot g_t，该段合计
k∑t=k+1igt=k (prei−prek)k \sum_{t=k+1}^{i} g_t = k\,(\text{pre}_i - \text{pre}_k)

其中 pre\text{pre} 是降序 gg 的前缀和。前 kk 人本身就是子问题 fk, j−(i−k)f_{k,\,j-(i-k)}（那 i−ki-k 块已被 1 块段占用）。枚举断点取最小：

fi,j=min⁡0⩽k<i{ fk, j−(i−k)+k (prei−prek) },j⩾i−kf_{i,j} = \min_{0 \leqslant k < i}\Big\{\, f_{k,\,j-(i-k)} + k\,(\text{pre}_i - \text{pre}_k) \,\Big\},\qquad j \geqslant i-k

两类转移互不重叠且覆盖所有可能。因为每人至少 1 块，只有 j⩾ij \geqslant i 可达；边界 f0,0=0f_{0,0} = 0，其余 +∞+\infty，答案即 fn,Mf_{n,M}。

样例的状态与转移。 排序后 gg 降序为 3,2,13,2,1，pre=[0,3,5,6]\text{pre} = [0,3,5,6]。下表列出小规模状态（∞\infty 表示不可达）：

i\ji \backslash j 0 1 2 3 4 5 6 7 8
0 0 — — — — — — — —
1 — 0 0 0 0 0 0 0 0
2 — — 0 2 0 2 0 2 0
3 — — — 0 3 2 0 2 2

取 f3,20f_{3,20}：先连续走 5 次情况 A（20→17→14→11→8→520 \to 17 \to 14 \to 11 \to 8 \to 5，每步 jj 减 i=3i=3，怨气不变），落到 f3,5=2f_{3,5} = 2；这次由情况 B 的 k=2k = 2 取得：f2,4+2 (pre3−pre2)=0+2×1=2f_{2,4} + 2\,(\text{pre}_3 - \text{pre}_2) = 0 + 2 \times 1 = 2，即位置 3 拿 1 块、上方有 2 人更多。剩下的 f2,4f_{2,4} 再走一次情况 A 到 f2,2f_{2,2}，最后由 k=0k=0 直接在怨气 00 处收尾。加上剥离的层数后，位置 1,21,2 得 1+6=71+6=7 块、位置 3 得 1+5=61+5=6 块。

位置（gg 降序） gg 最终块数 比自己多的人数 怨气
1 3 7 0 0
2 2 7 0 0
3 1 6 2 2

合计 22。代价全部落在贪婪度最小的那一位身上——这正是贪心排序要达到的效果。

输出方案。 转移只有两种来源，回推时从 (n,M)(n,M) 出发：若 j⩾2ij \geqslant 2i 且 fi,j=fi,j−if_{i,j} = f_{i,j-i}，说明该层是「全体减 1」，把层数 +1+1 并把 jj 减 ii；否则枚举出使情况 B 取到最小值的断点 kk，把位置 k+1..ik+1..i 的块数定为 1+extra1 + \text{extra}（extra\text{extra} 是此前剥离的层数）。由于 jj 每步严格减小，回推必然终止。

flowchart TD
    A["f[i][j]：前 i 人分 j 块"] --> B{"j >= 2i 且<br/>f[i][j-i] == f[i][j] ?"}
    B -- "是（情况 A）" --> C["全体减 1 块<br/>extra += 1，j -= i"]
    C --> A
    B -- "否（情况 B）" --> D["枚举断点 k：<br/>f[k][j-i+k] + k*(pre[i]-pre[k]) 取最小"]
    D --> E["位置 k+1..i 的块数定为 1+extra"]
    E --> F{"i == 0 ?"}
    F -- "否" --> A2["i = k，j -= i-k"]
    A2 --> A
    F -- "是" --> G["按原下标输出各人块数"]

图中两条出边对应两类转移；情况 A 可以连续走多次（本例走了 5 次），情况 B 每次结算一段「恰好 1 块」的后缀。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 分饼干：贪婪度降序排序后做「按块分配」的 DP，并沿最优决策回推方案。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll INF = 1000000000000000000LL / 4; // 「状态不可达」哨兵

ll n, m;
std::vector<ll> g;
std::vector<ll> order; // 贪婪度降序的下标排列
std::vector<ll> pre;   // pre[i] = 前 i 个人的贪婪度之和（按 order 顺序）
std::vector<std::vector<ll> > f;

bool greedy_less(ll x, ll y) {
    return g[x] > g[y]; // 贪婪度大的排在前面
}

// f[i][j] = 贪婪度降序的前 i 人恰好分到 j 块饼干时的最小怨气
void anger_table() {
    f.assign(n + 1, std::vector<ll>(m + 1, INF));
    f[0][0] = 0; // 前 0 人只有 j = 0 可达
    for (ll i = 1; i <= n; i++) {
        std::vector<ll> row(m + 1, INF);
        row[i] = 0; // 情况 B 的 k = 0：前 i 人各 1 块，怨气为 0
        // 情况 B：末尾 i-k 人各拿 1 块，合计 k * (pre[i] - pre[k])
        for (ll k = 1; k < i; k++) {
            ll weight = k * (pre[i] - pre[k]);
            for (ll j = i; j <= m; j++) {
                ll cand = f[k][j - i + k] + weight;
                if (cand < row[j]) row[j] = cand;
            }
        }
        // 情况 A：前 i 人都至少拿 2 块，集体减 1 块后大小关系不变
        for (ll j = 2 * i; j <= m; j++) {
            if (row[j - i] < row[j]) row[j] = row[j - i];
        }
        f[i] = row;
    }
}

// 沿最优决策回推，返回降序位置 1..n 上各人的饼干数
std::vector<ll> restore() {
    std::vector<ll> counts(n + 1, 0);
    ll extra = 0; // 已补回的「+1 层」数
    ll i = n, j = m;
    while (i) {
        // 情况 A：本层被「全体减 1 块」抹掉，回推时补一层
        if (j >= 2 * i && f[i][j - i] == f[i][j]) {
            extra++;
            j -= i;
            continue;
        }
        // 情况 B：断点 k 说明位置 k+1..i 各拿 1 块
        ll k = 0;
        for (ll t = 0; t < i; t++) {
            if (f[t][j - i + t] + t * (pre[i] - pre[t]) == f[i][j]) {
                k = t;
                break;
            }
        }
        for (ll pos = k + 1; pos <= i; pos++) {
            counts[pos] = 1 + extra;
        }
        j = j - i + k;
        i = k;
    }
    return counts;
}

int main() {
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    g.assign(n, 0);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &g[i]);
    }

    order.resize(n);
    for (ll i = 0; i < n; i++) order[i] = i;
    std::sort(order.begin(), order.end(), greedy_less);

    pre.assign(n + 1, 0);
    for (ll i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + g[order[i]];
    }

    anger_table();
    std::vector<ll> counts = restore();

    std::vector<ll> ans(n, 0);
    for (ll pos = 1; pos <= n; pos++) {
        ans[order[pos - 1]] = counts[pos]; // 换回输入顺序
    }

    printf("%lld\n", f[n][m]);
    for (ll i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
    return 0;
}
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 20:12
# update_at: 2026-10-01 20:47

import sys
from itertools import accumulate

INF = 10**30  # 「状态不可达」哨兵：比任何合法总怨气都大
CUTOFF = 16   # libstdc++ std::sort 的区间阈值：长度不超过它时只剩插入排序


def greedy_order(n: int, g: list[int]) -> list[int]:
    """贪婪度降序的下标排列，并列时复刻 libstdc++ std::sort 的顺序。

    本题并列最优方案极多，参考数据由标程里的非稳定排序产生，并列元素的先后
    决定了输出哪一个方案，所以必须逐位复刻该实现的比较与划分过程。
    """
    a = list(range(n))

    def less(x: int, y: int) -> bool:
        """降序比较：贪婪度大的排在前面。"""
        return g[x] > g[y]

    def median_to_first(first: int, last: int) -> None:
        """把 a[first+1]、a[mid]、a[last-1] 三者的中位数换到 a[first] 当枢轴。"""
        i, j, k = first + 1, (first + last) >> 1, last - 1
        if less(a[i], a[j]):
            pick = j if less(a[j], a[k]) else (k if less(a[i], a[k]) else i)
        else:
            pick = i if less(a[i], a[k]) else (k if less(a[j], a[k]) else j)
        a[first], a[pick] = a[pick], a[first]

    def partition(first: int, last: int, pivot: int) -> int:
        """双向夹逼：枢轴位置 pivot 全程不被交换，左侧都不小于它，返回右半段起点。"""
        while True:
            while less(a[first], a[pivot]):
                first += 1
            last -= 1
            while less(a[pivot], a[last]):
                last -= 1
            if first >= last:
                return first
            a[first], a[last] = a[last], a[first]
            first += 1

    def sift_down(first: int, pos: int, length: int) -> None:
        """大顶堆下沉：堆区是 a[first:first+length]，从 pos 处修复。"""
        val, child = a[first + pos], pos
        while child < (length - 1) >> 1:
            child = 2 * child + 1
            child += less(a[first + child], a[first + child + 1])
            if not less(val, a[first + child]):
                break
            a[first + pos] = a[first + child]
            pos = child
        a[first + pos] = val

    def heap_sort(first: int, last: int) -> None:
        """内省排序的兜底：递归深度用尽时改走堆排序。"""
        length = last - first
        if length > 1:
            for parent in range((length - 2) >> 1, -1, -1):
                sift_down(first, parent, length)
            while last - first > 1:
                last -= 1
                a[first], a[last] = a[last], a[first]
                sift_down(first, 0, last - first)

    def introsort(first: int, last: int, depth: int) -> None:
        """快排主体：右侧递归、左侧循环，深度耗尽转堆排序。"""
        while last - first > CUTOFF:
            if not depth:
                heap_sort(first, last)
                return
            depth -= 1
            median_to_first(first, last)
            cut = partition(first + 1, last, first)
            introsort(cut, last, depth)
            last = cut

    def linear_insert(last: int) -> None:
        """把 a[last] 插到左边已有序的区间里（左端必有哨兵，不必判越界）。"""
        val, pos = a[last], last - 1
        while less(val, a[pos]):
            a[pos + 1] = a[pos]
            pos -= 1
        a[pos + 1] = val

    def insertion_sort(first: int, last: int) -> None:
        """插入排序：首元素可能被反复挤到最前，故先单独处理一次。"""
        for i in range(first + 1, last):
            if less(a[i], a[first]):
                a[first], a[first + 1:i + 1] = a[i], a[first:i]
            else:
                linear_insert(i)

    if n > 1:
        introsort(0, n, 2 * (n.bit_length() - 1))
        insertion_sort(0, min(n, CUTOFF))
        for i in range(CUTOFF, n):
            linear_insert(i)
    return a


def anger_table(n: int, m: int, pre: list[int]) -> list[list[int]]:
    """f[i][j] = 贪婪度降序的前 i 人恰好分到 j 块饼干时的最小怨气，不可达记 INF。"""
    f = [[0] + [INF] * m]  # 前 0 人只有 j = 0 可达
    for i in range(1, n + 1):
        row = [INF] * (m + 1)
        row[i] = 0  # 情况 B 的 k = 0：前 i 人各 1 块，谁都没有比自己多的，怨气为 0
        # 情况 B：末尾 i-k 人各拿 1 块。这 i-k 人上面恰有 k 人比自己多，
        # 每人贡献 k 倍贪婪度，这段 1 块后缀合计 k * (pre[i] - pre[k])。
        for k in range(1, i):
            weight, base = k * (pre[i] - pre[k]), f[k]
            for j in range(i, m + 1):
                cand = base[j - i + k] + weight
                if cand < row[j]:
                    row[j] = cand
        # 情况 A：前 i 人都至少拿 2 块，集体减 1 块后大小关系不变，怨气也不变
        for j in range(2 * i, m + 1):
            if row[j - i] < row[j]:
                row[j] = row[j - i]
        f.append(row)
    return f


def restore(f: list[list[int]], n: int, m: int, pre: list[int]) -> list[int]:
    """沿最优决策回推，返回降序位置 1..n 上各人的饼干数；extra 是已补回的「+1 层」数。"""
    counts, extra = [0] * (n + 1), 0
    i, j = n, m
    while i:
        row = f[i]
        # 情况 A：本层被「全体减 1 块」抹掉，回推时补一层，记进 extra 而不是立刻加
        if j >= 2 * i and row[j - i] == row[j]:
            extra, j = extra + 1, j - i
            continue
        # 情况 B：断点 k 说明位置 k+1..i 各拿 1 块，再叠加此前所有 +1 层
        k = next(k for k in range(i) if f[k][j - i + k] + k * (pre[i] - pre[k]) == row[j])
        for pos in range(k + 1, i + 1):
            counts[pos] = 1 + extra
        i, j = k, j - i + k
    return counts


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    g = [next(data) for _ in range(n)]

    order = greedy_order(n, g)  # 贪婪度降序：贪婪的人拿得不比人少
    pre = [0, *accumulate(g[i] for i in order)]

    table = anger_table(n, m, pre)
    counts = restore(table, n, m, pre)

    ans = [0] * n
    for pos, idx in enumerate(order, 1):
        ans[idx] = counts[pos]  # 换回输入顺序输出

    print(table[n][m])
    print(*ans)


if __name__ == "__main__":
    solve()

复杂度

  • 时间复杂度 O(n2m)O(n^2 m)：状态 O(nm)O(nm) 个，情况 B 对每个状态枚举 kk，共 ∑ii=O(n2)\sum_{i} i = O(n^2) 次转移；n⩽30n \leqslant 30、M⩽5000M \leqslant 5000 时约 4.5×1064.5 \times 10^6 次。排序的 O(nlog⁡n)O(n \log n) 可忽略。
  • 空间复杂度 O(nm)O(nm)：存下整张表以便回推方案；若只需最小值可滚动到 O(m)O(m)。

gi⩽107g_i \leqslant 10^7、n⩽30n \leqslant 30，怨气上界约 30×107×30≈101030 \times 10^7 \times 30 \approx 10^{10}，超出 32 位但远在 64 位（以及 Python 任意精度整数）之内，无需取模。

总结

  • 核心是先贪心定序、再 DP：交换论证说明最优分配中 gg 越大块数越多，把「任意分配」压缩成「非增序列」。
  • 状态 fi,jf_{i,j} 的关键在于只按「末尾有多少人恰好拿 1 块」划分子集：情况 A 用「全体减 1 块、怨气不变」把 jj 降下来（fi,j=fi,j−if_{i,j} = f_{i,j-i}），情况 B 枚举断点 kk 一次性结算这段 1 块后缀（+k(prei−prek)+k(\text{pre}_i-\text{pre}_k)）。
  • 转移无环，回推时按同样的两种来源逆推即可还原最优分配。并列最优解很多，输出任意一组都合法；若要与给定参考数据逐字节一致，需要连「并列 gg 的排序次序」一起复刻标程实现。