这道题居然是蓝题
by 前排吃瓜 @ 2018-10-22 07:46:03
%%%%%
by 前排吃瓜 @ 2018-10-22 07:46:24
dd
by lk_liang @ 2018-10-22 15:01:54
dd
by lk_liang @ 2018-10-22 15:57:02
这个问题我是想不通了 如果有dalao看到这篇讨论 谢谢你点醒一下我 ~~快弱哭了~~
by lk_liang @ 2018-10-26 21:08:28
长期关注这篇讨论 谢谢dalao了
by lk_liang @ 2018-10-30 17:22:26
@[李科良](/space/show?uid=103308) 最后一次check 可能return
false 了 所以不是最优？？？
by dongjiajiedc @ 2018-11-02 07:50:40
```cpp
#include <iostream>
#include <vector>
using namespace std;
unsigned long long n,d,num,sum,h[50010],k[50010]; // k数组记录每块巧克力是什么时候吃的
bool check(long long x) // 每天的开心值至少是x
{
num=0,sum=0; // 记录已经吃了几个巧克力
for(int i=1;i<=d;i++) // 枚举每一天
{
sum/=2; // 维护每天的开心程度
while(sum<x) // 如果今天的开心值还没达到
{
sum+=h[++num];
if(num>n) return false; // x值太大了
k[num]=i;
}
}
return true; // 还可以再大点或刚刚好时
}
int main()
{
cin>>n>>d; // 有n块巧克力 一共吃d天
unsigned long long r=0,l=0,mid; // 巧克力开心值总和
for(int i=1;i<=n;i++) cin>>h[i],r+=h[i];
while(l<=r)
{
mid=(l+r)/2;
if(!check(mid)) r=mid-1; // 如果不成立
else l=mid+1; // 寻找最优解
}
cout<<r<<endl;
check(r);
if(num!=n) for(int i=num+1;i<=n;i++) k[i]=d;
for(int i=1;i<=n;i++) cout<<k[i]<<endl;
return 0;
}
```
最后r一定就是答案啊。。 因为最后快要结束二分的时候l==r 这时候他俩都是正确值 然后二分return true后l=mid+1结束二分 所以最后结束时一定是最优解啊 = =
by lk_liang @ 2018-11-02 07:56:56
@[dongjiajiedc](/space/show?uid=59030)
by lk_liang @ 2018-11-02 07:57:05
@[李科良](/space/show?uid=103308) check r不是为了记录答案吗
by dongjiajiedc @ 2018-11-02 08:12:09