Monthly Expense POJ3273
投稿日： 更新日:
問題：http://poj.org/problem?id=3273
問題
日間あり日目に必要な金額はです。個の予算を建てます。各予算は以上の連続する日を含みます。また、それぞれの日は１つの予算のみに含まれます。最も支出の多い予算の最小値を求めてください。
解法
最大の予算を以下とできるかを二分探索します。
何個の予算が必要になるかは貪欲に数えていきます。そして、個数が以下かを判定すれば良いです。
実装
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> a(n);
for(int i = 0;i < n; ++i){
cin >> a[i];
}
int ok = 1e9 + 100, ng = 0;
while(ok - ng > 1){
int mid = (ok+ng)/2;
int count = 1;
int sum = 0;
for(int i = 0;i < n; ++i){
if(a[i] > mid){
count = 1e9;
break;
}
sum += a[i];
if(sum > mid){
count++;
sum = a[i];
}
}
if(count <= m){
ok = mid;
}else{
ng = mid;
}
}
cout << ok << endl;
return 0;
}