http://poj.org/problem?id=3273
給你每天的花費(fèi)，讓你分成m組 要求各組的和中的最大值越小越好
二分查找
#include<iostream> using namespace std; const int N=100001; int n,m; bool toosmall(int k,int money[]) { int count=1;//k吧花費(fèi)分成的組數(shù)，開始為一組 int sum=0; for(int i=1;i<=n;++i) { if(sum+money[i]>k)//如果超過(guò)k 應(yīng)增加一組，所以count加一 sum更新重計(jì) { sum=money[i]; ++count; } else { sum=sum+money[i]; } } if(count>m)//組數(shù)太多說(shuō)明mid太小 return true; return false; } int main() { while(cin>>n>>m) { int money[N]; int high,low; high=0;//上界 low=0;//下界 for(int i=1;i<=n;++i) { cin>>money[i]; low=max(low,money[i]);//最大的那個(gè)為下界 high=high+money[i];//和為上界 } int mid=(high+low)/2; while(low<high) { if(toosmall(mid,money))//如果mid太小 { low=mid+1; } else//mid太大 或者正好 { high=mid; } mid=(high+low)/2; } cout<<mid<<endl; } return 0; }
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
