[USACO10FEB] Chocolate Eating S

题意

有 N 块巧克力，要在 D 天内按顺序吃完。第 i 块巧克力会让幸福值增加 H_i。

每天睡前记录当天幸福值，然后睡觉时幸福值会变成 $floor(happy / 2)$ 。一天可以吃多块巧克力，也可以不吃，但巧克力必须按编号顺序吃。

要求最大化 D 天中睡前幸福值的最小值，并输出任意一种达到最优值的吃巧克力日期安排。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <bits/stdc++.h>
using namespace std;

int n, d;
long long h[15];
int assignDay[15], bestAssign[15];
long long bestValue;

long long evalPlan() {
    long long happy = 0;
    long long mn = (1LL << 60);
    int idx = 1;

    for (int day = 1; day <= d; day++) {
        while (idx <= n && assignDay[idx] == day) {
            happy += h[idx];
            idx++;
        }
        mn = min(mn, happy);
        happy /= 2;
    }

    if (idx <= n) return -1;
    return mn;
}

void dfs(int idx, int lastDay) {
    if (idx > n) {
        long long val = evalPlan();
        if (val > bestValue) {
            bestValue = val;
            for (int i = 1; i <= n; i++) bestAssign[i] = assignDay[i];
        }
        return;
    }

    for (int day = lastDay; day <= d; day++) {
        assignDay[idx] = day;
        dfs(idx + 1, day);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> h[i];

    bestValue = -1;
    dfs(1, 1);

    cout << bestValue << '\n';
    for (int i = 1; i <= n; i++) {
        cout << bestAssign[i] << '\n';
    }

    return 0;
}

朴素解枚举每块巧克力在哪一天吃，适合小数据验证，但 N,D 都可达 50000，不能枚举方案。

这题可以二分答案。假设我们要判断“每天睡前幸福值是否都能至少为 X”。

检查 X 时，从第 1 天到第 D 天模拟：

如果当前幸福值已经不少于 X，这天可以不吃巧克力。
否则按顺序吃巧克力，直到幸福值第一次达到 X。
如果巧克力吃完仍达不到 X，说明 X 不可行。
当天结束后，睡觉使幸福值除以 2 向下取整。

为什么“第一次达到就停”是对的？因为固定目标 X 时，当天吃更多只会消耗后面的巧克力。刚达标就停，给后面留下最多资源。如果这种最省的吃法都失败，其他吃法也不会成功。

样例中检查 $X=24$

这张表展示样例中目标最低幸福值为 24 时的一种检查过程。

天数	起床幸福值	当天吃掉的幸福值	睡前幸福值
1	`0`	`10+40`	`50`
2	`25`	不吃	`25`
3	`12`	`13`	`25`
4	`12`	`22`	`34`
5	`17`	`7`	`24`

每天睡前都至少是 24，所以 24 可行。继续二分可以证明更大的值不可行。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 5;
int n, d;
long long h[MAXN];
int eatDay[MAXN];

bool check(long long need, bool savePlan) {
    long long happy = 0;
    int idx = 1;

    if (savePlan) {
        for (int i = 1; i <= n; i++) eatDay[i] = 0;
    }

    for (int day = 1; day <= d; day++) {
        while (happy < need && idx <= n) {
            happy += h[idx];
            if (savePlan) eatDay[idx] = day;
            idx++;
        }

        if (happy < need) return false;
        happy /= 2;
    }

    if (savePlan) {
        while (idx <= n) {
            eatDay[idx] = d;
            idx++;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        sum += h[i];
    }

    long long l = 0, r = sum;
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        if (check(mid, false)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    check(l, true);
    cout << l << '\n';
    for (int i = 1; i <= n; i++) {
        cout << eatDay[i] << '\n';
    }

    return 0;
}

复杂度

每次检查最多扫描 D 天和 N 块巧克力，复杂度 $O(N+D)$ 。

总时间复杂度 $O((N+D) log sumH)$ 。
空间复杂度 $O(N)$ 。

总结

这题的关键是把“最大化最低值”转成二分答案。

给定一个最低幸福值后，贪心检查很自然：每天只吃到刚好达标为止。这个策略保留后续巧克力最多，所以能正确判断可行性；找到最大可行值后，再运行一次同样的过程就能构造输出方案。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。