欢迎光临
我们一直在努力

P2985 [USACO10FEB] Chocolate Eating S

题目描述

Bessie 从公牛们那里收到了 NNN(1≤N≤5×1041 \\leq N \\leq 5\\times10^41≤N≤5×104)块巧克力,但她不想吃得太快,所以她计划在接下来的 DDD(1≤D≤5×1041 \\leq D \\leq 5\\times10^41≤D≤5×104)天内安排吃巧克力的日程,以使这些天中她每天的最低幸福值尽可能高。

Bessie 的幸福值是一个整数,初始为 000,每晚睡觉时会减半(如果有小数则向下取整)。然而,当她吃掉第 iii 块巧克力时,幸福值会增加整数 HiH_iHi​(1≤Hi≤1×1061 \\leq H_i \\leq 1\\times10^61≤Hi​≤1×106)。如果她在某天吃巧克力,那么当天的幸福值以吃完巧克力后的值为准。Bessie 坚持要按照收到巧克力的顺序来吃。

如果有多个最优解,输出任意一个即可。

考虑一个要在 555 天内吃完 555 块巧克力的例子,它们分别带来的幸福值为 (10,40,13,22,7)(10, 40, 13, 22, 7)(10,40,13,22,7)。

如果 Bessie 在第一天吃掉第一块巧克力(101010 幸福值),然后等待之后再吃其他巧克力,她第一天的幸福值就是 101010。

以下是一个最大化最低幸福值的完整安排:

第 111 天:起床时幸福值 000 → 吃掉 10+4010+4010+40 → 睡前幸福值 505050。

第 222 天:起床时幸福值 252525 → 不吃 → 睡前幸福值 252525。

第 333 天:起床时幸福值 121212 → 吃掉 131313 → 睡前幸福值 252525。

第 444 天:起床时幸福值 121212 → 吃掉 222222 → 睡前幸福值 343434。

第 555 天:起床时幸福值 171717 → 吃掉 777 → 睡前幸福值 242424。

这样得到的最低睡前幸福值是 242424,这是 Bessie 能做到的最好结果。

输入格式

  • 第 111 行:两个用空格分隔的整数:NNN 和 DDD。
  • 第 2∼N+12\\sim N+12∼N+1 行:第 i+1i+1i+1 行包含一个整数:HiH_iHi​。

输出格式

  • 第 111 行:一个整数,表示 Bessie 在接下来 DDD 天中能达到的最高最低幸福值。
  • 第 2∼N+12\\sim N+12∼N+1 行:第 i+1i+1i+1 行包含一个整数,表示 Bessie 吃掉第 iii 块巧克力的日期。

输入输出样例 #1

输入 #1

5 5
10
40
13
22
7

输出 #1

24
1
1
3
4
5

思路

最低幸福值尽可能高

所以采用二分,在二分时二分最低幸福值,在 check 中使用贪心策略判断能否保持此幸福值及以上。

代码

注意:如果最后一天还有剩余巧克力需要全部吃完

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n,d,h[50001],l,r,ans;
vector<int> a,b;
bool check(int x)
{
int cnt=0,j=1;
for(int i=1;i<=d;i++)
{
cnt/=2;
if(cnt<x)
{
for(;j<=n;)
{
cnt+=h[j++];
if(cnt>=x)
break;
}
if(cnt<x)
return false;
}
}
return true;
}
signed main()
{
cin>>n>>d;
for(int i=1;i<=n;i++)
cin>>h[i],r+=h[i];
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else
r=mid–1;
}
cout<<ans<<'\\n';
int cnt=0,j=1;
for(int i=1;i<=d;i++)
{
cnt/=2;
if(cnt<ans)
{
for(;j<=n;)
{
cout<<i<<'\\n';
cnt+=h[j++];
if(cnt>=ans)
break;
}
}
}
while(j<=n)
j++,cout<<d<<'\\n';
return 0;
}

赞(0)
未经允许不得转载:171主机测评 » P2985 [USACO10FEB] Chocolate Eating S
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址