CSU----H: 修路

H: 修路

Submit Page      Time Limit: 1 Sec       Memory Limit: 128 Mb       Submitted: 29       Solved: 16    

Description

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

Input

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

Output

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

Sample Input

24 3100 200 300 4009 4250 100 150 400 550 200 50 700 300      

Sample Output

400900      

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int road[310];
    int t;
    int n,m;
    scanf("%d",&t);
    while(t--)
    {
        int left=0,right=0;
        int i;
        scanf("%d %d",&m,&n);
        for(i=1;i<=m;i++)
        {
            scanf("%d",&road[i]);
            right+=road[i];//因為耗時最長的情況是隻有一個工程隊，是以最長時間為所有的相加
            if(road[i]>left)
            left=road[i];//耗時最短的情況是工程隊的數量大于等于路段數，是以就可以每個工程隊修一段，最短時間就是最最大的那段路了
        }
        int mid;
        int tot,sum;
        while(left<right)
        {
            mid=(left+right)/2;
            
         for(i=2,tot=n,sum=road[1];i<=m;i++)
         {
             if(sum+road[i]>mid)//tot為工程隊數量，當連續路段耗時超過mid時，就需要另外再用一個工程隊來修了
             {
                 tot--;
                 sum=road[i];
             }
             else sum+=road[i];//每超過就累加
         }
         if(tot<=0) left=mid+1;//小于等于0就是工程隊不夠用，也就是說mid小了，需要大點
         else right=mid;//大于0就是還有工程隊沒用上，也就說明mid是大了，還可以更小
        }
        printf("%d\n",left);
    }
    return 0;
}