2016: [Usaco2010]Chocolate Eating

时间:2022-03-08 21:17:52

2016: [Usaco2010]Chocolate Eating

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 224  Solved: 87
[Submit][Status][Discuss]

Description

贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完,而是打算制定一个计划,

使得在接下来的D天里,她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量,一开始的时候是0,当她每天晚上睡觉的时候,快乐指数会减半(奇数时向下取整)。贝西把她的巧克力按照收到的时间排序,并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候,她的快乐指数会增加Hj。每天可以吃任意多块巧克力,如何帮助贝西合理安排,使得D天内她的最小快乐指数最大呢?

举个例子:假设一共有五块巧克力,贝西打算在五天时间内将它们吃完,每块巧克力提

供的快乐指数分别为10,40,13,22,7。则最好的方案如F:

天数

起床时快乐指数

食用的巧克力

就寝时快乐指数

1
    2
    3
    4
    5

0
    25
    12
    12
    17

10+ 40
 
    13
    22
    7

50
    25
    25
    34
    24

五天内的最小快乐指数为24,这是所有吃法中的最大值。

Input

  第一行:两个用空格分开的整数:N和D,1≤N.D≤50000
  第二行到第N+1行:第1+1行表示第i块巧克力提供的快乐指数Hj,1≤Hi≤1000000

Output

  第一行:单个整数,表示贝西在接下来D天内的最小快乐指数的最大值
  第二行到第N+1:在第i+l行有一个整数,代表贝西应该在哪一天吃掉第i块巧克力。
    如果有多种吃法,则输出按照词典序排序后最靠后的方案

Sample Input

55
10
40
13
22
7

Sample Output

24
1
1
3
4
5

HINT

 

Source

Silver

题解:一开始很困惑该怎么弄,感觉有点没头绪,直到我发现了这道题的解貌似符合单调性——于是二分答案,先枚举最后结果,然后判断是否合法,然后输出

 var
i,j,k,n,d:longint;
l,r,m:int64;
a:array[..] of int64;
function check(x:int64):boolean;inline;
var a1,a2:int64;
begin
a1:=;a2:=;
for i:= to n do
begin
a1:=a1+a[i];
while (a1>=x) and (a2<=d) do
begin
a1:=a1 div ;
inc(a2);
end;
if a2>d then exit(true);
end;
exit(false);
end;
procedure put(x:int64);inline;
var a1,a2:int64;
begin
a1:=;a2:=;
for i:= to n do
begin
a1:=a1+a[i];
writeln(a2);
while (a1>=x) and (a2<d) do
begin
a1:=a1 div ;
inc(a2);
end;
end;
end;
begin
readln(n,d);
for i:= to n do readln(a[i]);
l:=;r:=;
for i:= to n do r:=r+a[i];
while l<=r do
begin
m:=(l+r) div ;
if check(m)=false then r:=m- else l:=m+;
end;
writeln(l-);
put(l-);
end.

2016: [Usaco2010]Chocolate Eating的更多相关文章

  1. BZOJ 2016&colon; &lbrack;Usaco2010&rsqb;Chocolate Eating

    题目 2016: [Usaco2010]Chocolate Eating Time Limit: 10 Sec  Memory Limit: 162 MB Description 贝西从大牛那里收到了 ...

  2. BZOJ 2016&colon; &lbrack;Usaco2010&rsqb;Chocolate Eating&lpar; 二分答案 &rpar;

    因为没注意到long long 就 TLE 了... 二分一下答案就Ok了.. ------------------------------------------------------------ ...

  3. 【BZOJ】2016&colon; &lbrack;Usaco2010&rsqb;Chocolate Eating(二分)

    http://www.lydsy.com/JudgeOnline/problem.php?id=2016 这些最大最小显然是二分. 但是二分细节挺多的...这里注意二分的区间,可以累计所有的可能,然后 ...

  4. bzoj 2016&colon; &lbrack;Usaco2010&rsqb;Chocolate Eating【二分&plus;贪心】

    二分答案,贪心判断,洛谷上要开long long #include<iostream> #include<cstdio> using namespace std; const ...

  5. bzoj2016&lbrack;Usaco2010&rsqb;Chocolate Eating&ast;

    bzoj2016[Usaco2010]Chocolate Eating 题意: n块巧克力,每次吃可以增加ai点快乐,每天早晨睡觉起来快乐值会减半,求如何使d天睡觉前的最小快乐值最大.n,d≤5000 ...

  6. &lbrack;Usaco2010&rsqb;Chocolate Eating

    题目描述 贝西从大牛那里收到了N块巧克力.她不想把它们马上吃完,而是打算制定一个计划, 使得在接下来的D天里,她能够尽量地快乐.贝西的快乐指数可以用一个整数来衡量,一开始的时候是0,当她每天晚上睡觉的 ...

  7. P2985 &lbrack;USACO10FEB&rsqb;吃巧克力Chocolate Eating

    P2985 [USACO10FEB]吃巧克力Chocolate Eating 题目描述 Bessie has received N (1 <= N <= 50,000) chocolate ...

  8. BZOJ2016&colon; &lbrack;Usaco2010 Feb&rsqb;Chocolate Eating

    [传送门:BZOJ2016] 简要题意: 贝西收到了N 块巧克力,她会在接下来的D 天里吃掉这些巧克力,她想制定一个计划,让她每 天的快乐度都保持在较高的水品上. 在第一天刚开始的时候,贝西的快乐度为 ...

  9. luogu P2985 &lbrack;USACO10FEB&rsqb;吃巧克力Chocolate Eating

    题目描述 Bessie拿到了N (1 <= N <= 50,000)块巧克力.她决定想个办法吃掉这些巧克力,使得它在吃巧克力的这段时间里,最不开心的一天尽可能的开心.并且一共吃D (1 & ...

随机推荐

  1. SpringMVC原理解析-Servlet容器启动时初始化SpringMVC应用的原理

  2. 历尽磨难之PL&sol;SQL链接Oracle数据库

    说起来都是泪啊,上司布置的任务需要远程连接Oracle数据库,说实话这又是我人生中的第一次.我听到以后觉得不是什么大问题,然而我错了..错的很厉害! 我搞了一天一夜才弄好,这里面原因有很多,大体来讲还 ...

  3. softwareTesting&lowbar;work2&lowbar;question1

    input类 package com.Phantom; import java.util.ArrayList; import java.util.HashMap; import java.util.L ...

  4. Android学习手记&lpar;4&rpar; BroadcastReceiver监听电池信息

    Android 中,Broadcast是一种在应用程序之间进行传输信息的机制.BroadcastReceiver对发送过来的Broadcast进行过滤和响应.根据这种机制,我们可以获取电池现有电量等信 ...

  5. DS-1

    一.作业题目 仿照三元组或复数的抽象数据类型写出有理数抽象数据类型的描述 (有理数是其分子.分母均为整数且分母不为零的分数). 有理数基本运算: 构造有理数T,元素e1,e2分别被赋以分子.分母值 销 ...

  6. mac OS 安装maven遇到问题e45&colon; &&num;39&semi;readonly&&num;39&semi; option is set

    1.下载 Maven, 并解压到某个目录.例如/Users/yintingting/apache-maven-3.3.9 2.打开Terminal,输入以下命令,设置Maven classpath v ...

  7. java中基础数据类型的应用

    1.float 与 double float是单精度类型,占用4个字节的存储空间  double是双精度类型,占用8个字节的存储空间  1)当你不声明的时候,默认小数都用double来表示,所以如果要 ...

  8. css笔记 - 张鑫旭css课程笔记之 z-index 篇

    一.z-index语法.支持的属性值等 z-index: 在支持z-index的元素上, z-index规定了元素(包括子元素)的垂直z方向的层级顺序, z-index可以决定哪个元素覆盖在哪个元素上 ...

  9. 初识PHP&lpar;二&rpar;常用函数

    在此记录一些常用库函数和常用语法以便查阅 一.PHP手册 php手册中文地址 http://php.net/manual/zh 二.一些常用操作 2.1字符串操作 2.1.1 strpos — 查找字 ...

  10. Unable to instantiate application com&period;android&period;tools&period;fd&period;runtime&period;BootstrapApplication 解决办法

    相信很多人都遇到过这个问题,用Android Studio正在运行程序的时候,突然不知道什么原因,报一个找不到application或者找不到activity的错误(java.lang.ClassNo ...