虽然是简单的二分搜索,但是还是需要注意细节。您的代码存在两个Bug,而且比较难发现,特别是您的思维已经陷入定势。
Bug1:
```
while(now<x&&c<=n) ans[c]=i,now+=a[c++];
```
在搜索的同时记录答案,这本来是没有错的,但是需要考虑以下情况:当前已经搜索得到了最优的不开心值,此时ans中存储的也是最佳答案,但是由于二分搜索的特性,可能还会进行一次搜索,使得最终ans里的前面一部分是正确值,只是从某个值开始产生错误,因为后续的搜索不是最优值,其吃法会覆盖原来的正确吃法,导致错误。
Bug2:有可能只需吃前面某些巧克力即可保持D天都能达到最优值,剩下的巧克力不吃也可以,但是题目要求必须吃完,那么可以安排将这些巧克力全部在第D天吃掉,您的程序没有考虑这种情况。
以下是在您的代码上修正而得,使用一个临时变量happiness来记录最优值,这是一个好的习惯,因为在二分搜索中,如果不这样做,往往要从left值或者right值去推断最优值,这样容易出错,而使用临时变量来记录最优值,不易发生错误。希望您在以后也这样做。
```cpp
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, d, a[50010], l, r = 0;
bool check(ll x)
{
int c = 1;
ll now = 0;
for (int i = 1; i <= d; i++)
{
while (now < x && c <= n) now += a[c++];
if (now < x) return false;
now /= 2;
}
return true;
}
int main()
{
cin >> n >> d;
for (int i = 1; i <= n; i++)
cin >> a[i], r += a[i];
ll happiness;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (check(mid))
{
happiness = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << happiness << '\n';
int c = 1;
ll now = 0;
for (int i = 1; i <= d; i++)
{
while (now < happiness && c <= n)
{
cout << i << '\n';
now += a[c++];
}
now /= 2;
}
for (int i = c; i <= n; i++) cout << d << '\n';
return 0;
}
```
@[⚡小林子⚡](/user/100910)
by metaphysis @ 2020-05-25 20:50:06
@[metaphysis](/user/333388) 太详细了,谢谢
by ⚡小林子⚡ @ 2020-05-25 20:52:35
已过,此帖完结
by ⚡小林子⚡ @ 2020-05-25 20:55:52
@[metaphysis](/user/333388) 大佬太强了,看到您的解释才过的,真是细节呀,万分感谢谢
by Echo_j @ 2021-09-03 14:47:50
@[metaphysis](/user/333388)
十分感谢!!
by Play_CP_4fun @ 2023-04-27 08:45:02