首页 > 代码库 > linux嵌入式驱动-总线设备驱动模型

linux嵌入式驱动-总线设备驱动模型

   一个农夫想要合理的理财,他给你未来N天的每天支出(1<=N<=100000), 并计划把这N天分成M个部分(1 <=M <=N)(每个部分的天数是连续的),要求求出这些部分里花费最和最大值最小,输出这个最大值。

100 400 300 100 500 101 400 可以这么划分(100 400) (300 100) (500) (101)(400) ,五个分组里最大值是500,这个划是最佳的了,因为在其他划分里肯定有部分是大于500的,如(100) (400 300) (100 500)(101) (400)。

分析:

       典型的二分,我们可以二分求最大值,上界是把所有的都分一组,也就是所有天数的和,下界是把每天当成一组的最大值。然后二分这个最大值,求解。

      关于如何判断mid值。 我们依照mid值来分组,如果当前部分的和大于了mid值,那么分组加一,在进行下一组的划分。二分能够找到最小的一个值使得恰好分成M组。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int M = 100005;

int a[M];
int n, m;

int group(int v)          //依照V值分组  返回分组数
{
    int cnt = 1;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        if (sum > v)
        {
            cnt++;
            sum = a[i];
        }
    }
    return cnt;
}

int bsearch(int l, int r)
{
    if (l == r)
        return l;
    int mid = (l+r)>>1;
    if (m >= group(mid))
        return bsearch(l, mid);
    else 
        return bsearch(mid+1, r);
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        int right = 0;
        int lift = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            right += a[i];                      //right是上界, lift是下界
            lift = max(lift, a[i]);
        }
        int ans = bsearch(lift, right);
        printf("%d\n", ans);
    }
    return 0;
}