Java教程

洛谷 P2440 木材加工(二分,含边界处理的笔记)

本文主要是介绍洛谷 P2440 木材加工(二分,含边界处理的笔记),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 题目链接:

木材加工 - 洛谷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;
}

这篇关于洛谷 P2440 木材加工(二分,含边界处理的笔记)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!