Binary Search
最大值最小化 => 二分搜尋
用二分搜去找到最低的最高花費。 check(d) 代表限制 fajomonth 最大的大小是 d ，是否能夠湊出數量 M 個 jajomonth 。
檢查的策略是，依序把每天的花費加起來，若有其中一天超過 d 則失敗，若發現 jajomonth 大小超過 d 則增加 jajomonth 數量，如果 jajomonth 的數量 > 題目的 M ，則失敗。
之後用二分搜找到 check(d) = true 的下界。
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
class Solution{
private:
vector<int>data;
int N, M;
inline void readIO(void) {
scanf("%d%d",&N,&M);
for(int i=0; i<N; ++i) {
int t; scanf("%d",&t);
data.push_back(t);
}
}
bool check(int d) {
int counter=1;
int sum=0;
for(int i=0; i<N; ++i) {
if(data.at(i)>d) return false;
int t=sum+data.at(i);
if(t <= d ) sum+=data.at(i);
else { // t > d
sum=data.at(i);
++counter; // start new set
}
if(counter>M) return false;
}
return true;
}
int sol(void) {
int lb=0, ub=1e9+7;
while(ub-lb>1) {
int mid=((unsigned int)lb+(unsigned int)ub)>>1;
if(check(mid)) ub=mid;
else lb=mid;
}
return ub;
}
public:
void mainLoop(void) {
data.clear();
readIO();
printf("%d\n", sol());
}
};
int main(void) {
Solution sol;
sol.mainLoop();
return 0;
}