UVa11413 Fill the Containers
問題
http://uva.onlinejudge.org/external/114/11413.html
概要
解法
#include <bits/stdc++.h> using namespace std; #define LLINF (LONG_LONG_MAX/4) #define ALL(c) (c).begin(), (c).end() #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; int N, M; vector<ll> vessel; bool eval(ll x) { int c_cnt = 1; ll sum = 0; rep(i, N) { if(sum + vessel[i] > x) { c_cnt ++; sum = 0; } sum += vessel[i]; } return c_cnt <= M; } int main() { while(cin >> N >> M) { vessel.resize(N); rep(i, N) cin >> vessel[i]; ll l = *max_element(ALL(vessel)), r = LLINF; rep(i, 100) { ll mid = (l+r)/2; if(eval(mid)) { r = mid; } else { l = mid; } } cout << r << endl; } return 0; }