题目链接

整点巧克力

题目描述

有 块巧克力和 天。第 块巧克力的快乐值为 。

每天开始时，前一天的快乐值会减半（向下取整）。在当天，可以按顺序吃掉若干块巧克力（也可以不吃），增加相应的快乐值。

要求设计一个方案，将所有 块巧克力在 天内吃完，使得这 天中，每天结束时最小的快乐值最大。

输出这个最大化的最小值，以及该方案下每块巧克力是在哪一天吃的。

解题思路

这是一个典型的最大化最小值问题，我们可以使用二分答案来解决。

我们二分最终的答案，即“最小快乐值” 。对于一个给定的 ，我们需要一个 check 函数来判断：是否存在一种吃巧克力的方案，使得每天结束时的快乐值都不小于 。

check(X) 函数的逻辑具有单调性，这保证了二分答案的正确性。

check(X) 函数的实现可以采用贪心策略。由于巧克力必须按顺序吃，我们的决策过程是确定的。

  1. check 函数的任务是判断能否存活 天，即保证这 天每天结束时的快乐值都不小于 。
  2. 我们模拟从第 天到第 天。对于每一天，我们贪心地吃下最少数量的巧克力，恰好使得当天的快乐值大于或等于 。
  3. 如果在某一天，即使吃完了所有剩下的巧克力，快乐值仍然小于 ，则说明无法存活，check(X) 返回 false。
  4. 如果成功地度过了 天，那么 check(X) 就返回 true。注意，此时我们不关心是否所有巧克力都被吃完了。因为如果能满足 天的约束，那么任何剩余的巧克力都可以被安排在第 天吃掉，这只会使第 天的快乐值更高，不会违反约束。

方案构造 在通过二分查找确定了最优的最小快乐值 ans 之后，我们需要构造具体的方案。

  1. 我们重新模拟一遍从第 天到第 天的过程。
  2. 对于每一天，我们同样贪心地吃下必需的巧克力，使得快乐值恰好不小于 ans。每吃掉一块巧克力，就记录下它是在哪一天被吃掉的。
  3. 这个模拟过程结束后，可能会有巧克力剩下。这些剩下的巧克力都是在满足每日基本需求之外的，我们将它们全部安排在最后一天（第 天）吃掉即可。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 简化 check：只检查是否能存活 d 天
bool check(long long x, int n, int d, const vector<int>& h) {
    long long current_happiness = 0;
    int chocolate_idx = 0;
    for (int day = 1; day <= d; ++day) {
        current_happiness /= 2;
        while (current_happiness < x && chocolate_idx < n) {
            current_happiness += h[chocolate_idx];
            chocolate_idx++;
        }
        if (current_happiness < x) {
            return false; // 无法存活这一天
        }
    }
    return true; // 成功存活 d 天
}

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> h(n);
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
        total_sum += h[i];
    }

    long long left = 0, right = total_sum;
    while (left < right) {
        long long mid = left + (right - left + 1) / 2;
        if (check(mid, n, d, h)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    long long ans = left;

    cout << ans << endl;

    // 构造方案
    vector<int> p(n);
    long long current_happiness = 0;
    int chocolate_idx = 0;
    for (int day = 1; day <= d; ++day) {
        current_happiness /= 2;
        while (chocolate_idx < n && current_happiness < ans) {
            current_happiness += h[chocolate_idx];
            p[chocolate_idx] = day;
            chocolate_idx++;
        }
    }
    // 将剩余的巧克力安排在最后一天
    while (chocolate_idx < n) {
        p[chocolate_idx] = d;
        chocolate_idx++;
    }
    for (int i = 0; i < n; ++i) {
        cout << p[i] << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    private static boolean check(long x, int n, int d, int[] h) {
        long currentHappiness = 0;
        int chocolateIdx = 0;
        for (int day = 1; day <= d; ++day) {
            currentHappiness /= 2;
            while (currentHappiness < x && chocolateIdx < n) {
                currentHappiness += h[chocolateIdx];
                chocolateIdx++;
            }
            if (currentHappiness < x) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[] h = new int[n];
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
            totalSum += h[i];
        }

        long left = 0, right = totalSum;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (check(mid, n, d, h)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        long ans = left;

        System.out.println(ans);

        // 构造方案
        int[] p = new int[n];
        long currentHappiness = 0;
        int chocolateIdx = 0;
        for (int day = 1; day <= d; ++day) {
            currentHappiness /= 2;
            while (chocolateIdx < n && currentHappiness < ans) {
                currentHappiness += h[chocolateIdx];
                p[chocolateIdx] = day;
                chocolateIdx++;
            }
        }
        // 将剩余的巧克力安排在最后一天
        while (chocolateIdx < n) {
            p[chocolateIdx] = d;
            chocolateIdx++;
        }

        for (int i = 0; i < n; i++) {
            System.out.println(p[i]);
        }
    }
}

def check(x, n, d, h):
    current_happiness = 0
    chocolate_idx = 0
    for day in range(1, d + 1):
        if current_happiness < 0:
            current_happiness = 0
        current_happiness //= 2
        while current_happiness < x and chocolate_idx < n:
            current_happiness += h[chocolate_idx]
            chocolate_idx += 1
        
        if current_happiness < x:
            return False
    return True

def main():
    n, d = map(int, input().split())
    h = [int(input()) for _ in range(n)]

    left, right = 0, sum(h)
    while left < right:
        mid = (left + right + 1) // 2
        if check(mid, n, d, h):
            left = mid
        else:
            right = mid - 1
    ans = left

    print(ans)

    # 构造方案
    p = [0] * n
    current_happiness = 0
    chocolate_idx = 0
    day = 1
    while chocolate_idx < n and day <= d:
        current_happiness //= 2
        while chocolate_idx < n and current_happiness < ans:
            current_happiness += h[chocolate_idx]
            p[chocolate_idx] = day
            chocolate_idx += 1
        day += 1
    
    # 将剩余的巧克力安排在最后一天
    while chocolate_idx < n:
        p[chocolate_idx] = d
        chocolate_idx += 1

    for day_val in p:
        print(day_val)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：二分答案 + 贪心。
  • 时间复杂度：，其中 是所有巧克力快乐值的总和。二分查找需要进行 次迭代，每次迭代内部的 check 函数对巧克力数组进行一次线性扫描，耗时 。
  • 空间复杂度：，用于存储巧克力的快乐值数组和最终的方案。