題干：

前段時間，某省發(fā)生干旱，B山區(qū)的居民缺乏生活用水，現(xiàn)在需要從A城市修一條通往B山區(qū)的路。假設(shè)有A城市通往B山區(qū)的路由m條連續(xù)的路段組成，現(xiàn)在將這m條路段承包給n個工程隊（n?≤?m?≤ 300）。為了修路的便利，每個工程隊只能分配到連續(xù)的若干條路段（當(dāng)然也可能只分配到一條路段或未分配到路段）。假設(shè)每個工程隊修路的效率一樣，即每修長度為1的路段所需的時間為1。現(xiàn)在給出路段的數(shù)量m，工程隊的數(shù)量n，以及m條路段的長度（這m條路段的長度是按照從A城市往B山區(qū)的方向依次給出，每條路段的長度均小于1000），需要你計算出修完整條路所需的最短的時間（即耗時最長的工程隊所用的時間）。

Input

?

第一行是測試樣例的個數(shù)T?，接下來是T個測試樣例，每個測試樣例占2行，第一行是路段的數(shù)量m和工程隊的數(shù)量n，第二行是m條路段的長度。

Output

?

對于每個測試樣例，輸出修完整條路所需的最短的時間。

Sample Input

2 4 3 100 200 300 400 9 4 250 100 150 400 550 200 50 700 300

Sample Output

400 900

Hint

?

解題報告：

? ?二分找到答案。因為我這里是l從0開始的，所以fit中需要先循環(huán)判斷一遍是否單個路段的滿足。而如果讀數(shù)據(jù)的時候維護一個maxx，然后l從maxx開始，那就不需要fit函數(shù)中這個第一個for的這一行了。

AC代碼：

#include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std;int n,m,sum,l,r;//m個線段，最多分成n段、 int a[305]; bool fit(int x) {int cnt = 1,cur=0;for(int i = 1; i<=m; i++) if(a[i] > x) return 0;for(int i = 1; i<=m; i++) {if(cur+a[i] <= x) cur+=a[i];else cnt++,cur=0,i--;}if(cnt > n) return 0;else return 1; } int main() {int t;cin>>t;while(t--) {sum = 0;scanf("%d%d",&m,&n);for(int i = 1; i<=m; i++) {scanf("%d",&a[i]);sum += a[i];}l=0,r=sum;int mid = (l+r)/2;while(l<r) {mid = (l + r) / 2;if(fit(mid)) r=mid;else l=mid+1;}printf("%d\n",l);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【CSU - 1023】【HRBUST - 1039】修路（二分，枚举）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。