首页 > [USACO 2010 Feb S]Chocolate Eating
开通博客写题解
头像 SSuryxin
发表于 2021-05-05 19:02:18
Chocolate Eating 题目描述： Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she want 展开全文
去ta的博客 赞 (6) 回复(3) 收起
头像 夜语声烦-
发表于 2022-05-12 17:23:05
[USACO 2010 Feb S]Chocolate Eating 二分的对象是幸福感 #include <iostream> using namespace std; typedef long long LL;//啥也不说了，直接全部long long const int N = 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-06-07 18:32:21
二分 首先假设已经求解到的ans代表合理的最大幸福的，我们显然希望找到一个吃巧克力的方式让他比当前ans更大，否则只能更小。符合二分性质。而且二分的check函数设计直接把吃过的sum每天减半如果不够了再吃一个新的巧克力，看最后会不会超过n即可 最后调用一次check求道合理的最大幸福度的安排方法。 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 Xiaoxina
发表于 2021-04-18 10:58:02
题意：贝西从bulls那里收到了N块巧克力。她不想把它们马上吃完，而是打算制定一个计划，使得在接下来的D天里，使得每天的最小快乐值最大。贝西的快乐指数可以用一个整数来衡量，一开始的时候是0，当她每天晚上睡觉的时候，快乐指数会减半（奇数时向下取整）。贝西把她的巧克力按照收到的时间排序，并坚持按照这个顺 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 RVCake
发表于 2022-03-15 15:41:14
解题思路 二分枚举+检验的典型例题。 首先考虑边界问题，最大的情况是 5e105e105e10 的快乐值，但是实际上可以在读入的时候就对巧克力的快乐值进行累计，这样得到的就是可能存在的最大解，因为每过一天快乐值都会减半所以最大值不会超过巧克力快乐值总数； 其次是二分的写法问题，题卡了好几天换了好几 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 菜鸡aaa
发表于 2023-07-17 11:06:02
1、显然最小幸福度范围是0~5e10，二分找出满足check(int x)条件的最大x即可。 2、check(int x)函数，用sum表示当天的幸福度，遍历每一天，确保每一天的幸福度都达到x即可 3、如果sum<x则表明当天幸福度不够，需要吃掉一个巧克力，sum+=h[i]直到sum> 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 装糊涂高手_
发表于 2022-03-31 17:44:56
典型二分答案+检验题 注意要点： 1、按顺序吃巧克力； 2、巧克力要吃完； 3、二分检验的时候注意看最后一次循环判断的是否是最终的二分答案，如果不是的话在跳出循环之后还得对最终的二分答案进行一次判断（因为吃巧克力的顺序在判断的时候生成，如果最后一次判断的不是最终的二分答案，那么吃巧克力的顺序对应的就 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-05 10:36:16
求最小幸福值的最大值，本题中只需要以答案入手去二分答案即可。 至于如何验证：从第一天开始遍历，如果幸福值小于给定的最小幸福值那么就吃巧克力就完了。 看最后是巧克力被先吃完，还是能够满足贝西每天的幸福值需要。 需要注意的是在记录记录每天吃巧克力的方案的时候前提是需要验证通过。因为最后结果有可 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 三大爷的剑
发表于 2021-10-12 17:52:41
技巧     二分 思路     尝试快乐值 x   ， 看是否每天都能达到。 二分找到满足条件的最大的值 实现 package main import ( "bufio" .  展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”