【CSU-1023】解题报告（二分）

原始题目

1023: 修路

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 632
  • Solved: 340 ### 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

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

Sample Output

400
900

Hint

Source

中南大学第四届大学生程序设计竞赛

解题思路

  • 每个队伍必须连续修路，每个队伍效率相同（每天都修单位长度）
  • 可以得到修路的下限和上限，二分修路长度最终得到答案

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e5+5;
int t,n,m;
int road[maxn];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(road,0,sizeof(road));
		scanf("%d%d",&m,&n);
		int high=0,low=0;
		for(int i=0;i<m;i++)
		{
			scanf("%d",&road[i]);
			high+=road[i];
			low=max(road[i],low);
		}
		while(low<high) //二分修路的长度 
		{
			
			int mid=(high+low)>>1;
//			printf("now mid=%d\n",mid);
			int tot=n-1,sum=road[0]; //一共还有n-1个人可以用 
			for(int i=1;i<m;i++)
			{
				if(sum+road[i]>mid)
				{
					tot--;
					sum=road[i];
				}
				else sum+=road[i];
				if(tot<0) break;
			}
			if(tot<0) low=mid+1;
			else high=mid;
		}
		printf("%d\n",low);
		
	}
 }

收获与反思

  • 二分思维转换
  • 已知上界下界后利用二分逼近答案