NOIP2017普及组初赛 完善程序 第2题 《切割绳子,二分法》

Keywords: NOIP2017普及组初赛完善程序 第2题，二分法

#include <iostream>

using namespace std;

int n, m, i;
int lbound, ubound, mid, count;
int len[100];

int main()
{
    cin >> n;
    count = 0;
    for (i = 0; i < n; i++)
    {
        cin >> len[i];
        count++;   // 1.填空 
    }

    cin >> m;
    if (m > count)  // 2.填空 
    {
        cout << "Failed" << endl;
        return 0;
    }

    lbound = 1;
    ubound = 1e6;
    while (lbound < ubound)  // 3.填空 
    {
        mid = lbound + ubound + 1 >> 1;  // 4.填空 
        count = 0;
        for (i = 0; i < n; i++) count += len[i] / mid; // 5.填空 
        if (count < m) ubound = mid - 1;  // 答案count落在m左侧，更新右端点 
        else lbound = mid;  //更新 l = mid，这个时候回想模板，  mid = l + r + 1 >> 1; 
    }
    cout << lbound << endl;

    return 0;
}

分析：二分法在考试题中经常出现，同时本身也是一个非常实用的算法，需要扎实掌握。

几个比较重要的点：

1. count += len[i] / mid; 每一段绳子，看能切割出来多少条mid
2. mid的取值，先取mid = lbound + ubound >> 1 ，check()，看count < m的性质，count 大于等于m的时候，答案落在mid的右侧，左端点lbound 更新为 mid， 那么mid = lbound + ubound + 1 >> 1（避免死循环）

update: 2019.10.14

补充一下：为什么mid 这个等式不加1就会死循环呢，回想一下整数除法，是下取整。mid = l + r >> 1，如果l r是相邻的两个整数，mid的值会取l，然后check()判断，让l更新为mid，那么也就是说mid = l,然后l又被=mid，这不就造成死循环了吗

所以需要mid = l + r + 1 >> 1这样，当l 和r 相差1的时候，mid也会倔强的向前移动一步。移动一步就会影响到check()的结果，进而，影响到r的更新，进而，l < r判断条件为否，跳出循环，结束战斗