P5161: 吃糖-训练套题T4T4
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
4. [吃糖ceafing.pas/
c/cpp]
【问题描述】
Bessie有
N(1≤
N≤
50,000)颗糖果，编号
1．．
N，但她不打算马上吃光，而是计算在接下来的
D(1≤
D≤
50,000)天按糖果编号从小到大逐天吃，当然，
Bessie以一天连续吃多颗糖果，也可以不吃，但不能跳着糖果来吃，要按糖果顺序吃。
吃了糖果
i，
Bessie's的能量值会增加
H_i(1≤
H_i≤
1，
000,000)。
Bessie都是在白天吃糖果，然后晚上睡觉，第二天醒来，她的能量值会变成前一天的能量值的一半
(向下取整
)。
Bessie's的能量值会累加。请你决定第
i颗糖果应该是第几天吃，才能使得
Bessie在这
D个晚上里，能量值最小的那个晚上
(假设是第
x个晚上
)，第
x个晚上的能量值最大
?输出该值，并且输出第
1(1≤
i≤
N)颗糖果是
Bessie第几天吃掉的。
例如：有
5个糖果，能量值分别是：
(10，
40，
13，
22，
7)。
Bessie按以下方式吃糖果，将会得到最优值：
第几天
醒来时能量值
吃了糖果后能量值
晚上睡觉能量值
1 0 10+40 50
2 25 ----- 25
3 12
13 25
4 12 22
34
5 17 7 24
可以看出，第
1天吃了糖果
1、糖果
2，第
2天不吃糖果，第
3天吃了糖果
3，第
4天吃了糖果
4，第
5天吃了糖果
5。那么在这
5个晚上，能量值最低的是第
5个晚上，能量值是
24，所以输出
24。然后你还要输出第
1(1≤
i≤
N)颗糖果是
Bessie第几天吃掉的。
【输入数据】
第
1行：两个整数：
N和
D
第
2．．
N+1行：每行一个整数
H_i。
【输出数据】
第
l行：一个整数，在这
D个晚上里，能量值最小的那个晚上
(假设是第
X个晚上
)，第
x个晚上的能量值最大可以是多少
?
第
2．．
N+1行：每行一个整数，第
i行表示第
i颗糖果是第几天被吃的。
【输入样例】
5 5
10
40
13
22
7
【输出样例】
24
1
1
3
4
5
【提示】
ceafing
算法分析：
本题可以用二分答案去解决。当我们知道答案后，贪心地去吃糖果，从左往右扫描糖
果，如果当前的能量没有达到答案，那么必须把当前的那颗糖果吃掉，如果当前的能量已
经达到了答案，那么当天没有必要再吃当前的那颗糖果，留着第二天吃更好。如此扫描下
去，看最后能维持的天数是否达到题目给出的天数d，如果达到，则是可行的，否则是不可行。时间复杂度是O(NlogN)。