【POJ 3273】 Monthly Expense (二分)

一個農民有塊地 他列了個計劃表 每天要花多少錢管理 但他想用m個月來管理 就想把這個計劃表切割成m個月來完畢 想知道每一個月最少花費多少 每一個月的花費是這個月的花費加和 必須按計劃表的順序來

全部天中花費中最大花費作為下界 全部花費加和作為上界 二分上下界間的花費可能 找出最少每月花費就可以

代碼例如以下:

#include <iostream> #include <cstdio>using namespace std;int ned[100000],n,m;bool can(int x)//推斷是否可行 {int i,sum = 0,cnt = 1;for(i = 0; i < n; ++i){sum += ned[i];if(sum > x)//加上這天后此劃分超過x 割開{sum = ned[i];cnt++;}}if(cnt > m) return false;//劃分塊數>m 不可行return true; }int main() {//freopen("in.in","r",stdin);int l,r,i,mid,ans;scanf("%d %d",&n,&m);r = l = 0;for(i = 0; i < n; ++i){scanf("%d",&ned[i]);r += ned[i];l = max(l,ned[i]);}while(l <= r){mid = (l+r)>>1;if(can(mid)) //可按mid劃分的時候 此題數據真水 開始二分寫挫了 還過了 3 2 4 4 4這組就能卡掉{ans = mid;r = mid-1;}else l = mid+1;}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/lxjshuju/p/7066545.html

總結

以上是生活随笔為你收集整理的【POJ 3273】 Monthly Expense (二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。