题意：有N个farm，每个farm花销farm[i]元。要求分成M块，尽可能让每个块花销少,求M个块中的最大值。（最大化最小值）
做法：二分结果（左界），每次判断mid能形成几个块，如果cur > M，说明钱必须更大，让块变少（low = mid + 1）；否则满足条件，继续寻找更小的值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>#include <algorithm>#include <stdio.h>#include <math.h>#define scf1(a) scanf("%d",&a)#define scf2(a,b) scanf("%d%d",&a,&b)using namespace std;int n, m;int farm[100100];bool judge(int mid){ int sum = 0, cur = 1; //cur初始化为1不是0啊！当满mid时 + 1 for(int i = 0; i < n; i++){ sum += farm[i]; if(sum > mid){ //超过mid，cur + 1， 更新sum sum = farm[i]; cur++; } } if(cur > m) return false; //钱必须更大，让区域块变少 low = mid + 1 else return true; //钱可以更小，让区域块变多 high = mid}int main(){ scf2(n, m); int low = 0, high = 0; for(int i = 0; i < n; i++){ scf1(farm[i]); low = max(low, farm[i]); high += farm[i]; } while(low < high){ int mid = (low + high) >> 1; if( judge(mid) ) high = mid; else low = mid + 1; } printf("%d
",high);} |