PKU 3273 Monthly Expense
http://poj.org/problem?id=3273
nヶ月間の必要経費が与えられる。
この期間を1ヶ月以上の連続する区間m個に分ける。
このとき、区間1個に含まれる必要経費の合計の最大値が最も小さくなるときの値はいくつかを求めるというような問題。
整数の二分探索は苦手です。
あまり上手く書けた試しがありません。
ll in[100000]; main(){ int n,m; cin>>n>>m; ll u=1,l=0; rep(i,n){ cin>>in[i]; u+=in[i]; l=max(l,in[i]); } while(l<u){ ll mid=(l+u)/2; int tm=1; ll tsum=0; rep(i,n){ if(tsum+in[i]>mid){ tsum=in[i]; ++tm; }else tsum+=in[i]; } if(tm>m)l=mid+1; else u=mid; } cout<<l<<endl; }