CSU----H: 修路

ゞ浴缸里的玫瑰 2022-06-14 20:09 133阅读 0赞

## 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;
    }