2016: [Usaco2010]Chocolate Eating

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

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

 1 var
 2    i,j,k,n,d:longint;
 3    l,r,m:int64;
 4    a:array[0..50010] of int64;
 5 function check(x:int64):boolean;inline;
 6          var a1,a2:int64;
 7          begin
 8               a1:=0;a2:=1;
 9               for i:=1 to n do
10                   begin
11                        a1:=a1+a[i];
12                        while (a1>=x) and (a2<=d) do
13                              begin
14                                   a1:=a1 div 2;
15                                   inc(a2);
16                              end;
17                        if a2>d then exit(true);
18                   end;
19               exit(false);
20          end;
21 procedure put(x:int64);inline;
22           var a1,a2:int64;
23           begin
24                a1:=0;a2:=1;
25                for i:=1 to n do
26                    begin
27                         a1:=a1+a[i];
28                         writeln(a2);
29                         while (a1>=x) and (a2<d) do
30                               begin
31                                    a1:=a1 div 2;
32                                    inc(a2);
33                               end;
34                    end;
35           end;
36 begin
37      readln(n,d);
38      for i:=1 to n do readln(a[i]);
39      l:=0;r:=0;
40      for i:=1 to n do r:=r+a[i];
41      while l<=r do
42            begin
43                 m:=(l+r) div 2;
44                 if check(m)=false then r:=m-1 else l:=m+1;
45            end;
46      writeln(l-1);
47      put(l-1);
48 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列

1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列 Time Limit: 5 Sec  Memory Limit:...

3387
来自专栏ml

HDUOJ-----4512吉哥系列故事——完美队形I(LCIS)

吉哥系列故事——完美队形I Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3276...

2918
来自专栏HansBug's Lab

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 Time Limit: 3 Sec  Memory ...

2868
来自专栏章鱼的慢慢技术路

牛客网2018年全国多校算法寒假训练营练习比赛(第二场)

3534
来自专栏ml

hdu-----(4514)湫湫系列故事——设计风景线(树形DP+并查集)

湫湫系列故事——设计风景线 Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/3276...

3878
来自专栏数据结构与算法

BZOJ2152: 聪聪可可(点分治)

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

963
来自专栏JackieZheng

Hadoop阅读笔记(二)——利用MapReduce求平均数和去重

前言:圣诞节来了,我怎么能虚度光阴呢?!依稀记得,那一年,大家互赠贺卡,短短几行字,字字融化在心里;那一年,大家在水果市场,寻找那些最能代表自己心意的苹果香蕉梨...

3076
来自专栏C语言及其他语言

【每日一题】问题 1146: 舍罕王的失算

关注我们 题目描述 相传国际象棋是古印度舍罕王的宰相达依尔发明的.舍罕王十分喜爱象棋,决定让宰相自己选择何种赏赐.这位聪明的宰相指着8*8共64格的象棋说:陛...

34311
来自专栏数据结构与算法

Day3上午解题报告

预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

2935
来自专栏HansBug's Lab

1230: [Usaco2008 Nov]lites 开关灯

1230: [Usaco2008 Nov]lites 开关灯 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: ...

2838

扫码关注云+社区

领取腾讯云代金券