http://poj.org/problem?id=3273
給你每天的花費，讓你分成m組 要求各組的和中的最大值越小越好
二分查找
#include<iostream> using namespace std; const int N=100001; int n,m; bool toosmall(int k,int money[]) { int count=1;//k吧花費分成的組數，開始為一組 int sum=0; for(int i=1;i<=n;++i) { if(sum+money[i]>k)//如果超過k 應增加一組，所以count加一 sum更新重計 { sum=money[i]; ++count; } else { sum=sum+money[i]; } } if(count>m)//組數太多說明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]);//最大的那個為下界 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; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
