木材加工 - 洛谷https://www.luogu.com.cn/problem/P2440
非常简单的题目,用left和right控制二分边界,ans一开始是0,每次check到符合题意结果都更新ans的值,看起来没有任何问题。
但是我当时写的时候re了,看了半天也没看出问题。后来队友帮我debug,才发现是边界处理不到位。左边界left一开始设置成了0而不是1,导致了 /0的错误。
1.re不一定是数组越界,还有可能是 /0错误。
2.学习到了一些debug技巧,打印ans日志的时候,发现少输出了一个数,是因为最后一次ans计算的时候出现 /0错误,导致中断了,我由此发现了这个问题。
以下是修改之后的ac代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5; ll len[maxn]; ll n, k; bool check(int mid){ ll ans = 0; for(int i=1; i<=n; i++){ ans += len[i]/mid; } if(ans >= k) return true; else return false; } int main(){ cin >> n >> k; //特别注意这里的left要设为1,不能是0,否则check函数中会出现 /0 的错误 //右边界设为0没有关系,因为如果一直是0,后面进入不了while循环,不会出问题 ll left = 1, right = 0; for(int i=1; i<=n; i++){ cin >> len[i]; right = max(right, len[i]); } ll ans = 0; while(left <= right){ int mid = left + (right-left)/2; if(check(mid)) {left = mid+1; ans = mid;} else right = mid-1; } cout << ans << endl; }