求助,只有40

P2985 [USACO10FEB] Chocolate Eating S

虽然是简单的二分搜索,但是还是需要注意细节。您的代码存在两个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


|