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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。