音乐网站开发开发,牌具做网站可以吗,上海广告公司,电脑上怎么重新安装wordpress题干#xff1a;
前段时间#xff0c;某省发生干旱#xff0c;B山区的居民缺乏生活用水#xff0c;现在需要从A城市修一条通往B山区的路。假设有A城市通往B山区的路由m条连续的路段组成#xff0c;现在将这m条路段承包给n个工程队#xff08;n ≤ m ≤ 300#xff09;。…题干
前段时间某省发生干旱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 300Sample Output
400
900Hint 解题报告 二分找到答案。因为我这里是l从0开始的所以fit中需要先循环判断一遍是否单个路段的满足。而如果读数据的时候维护一个maxx然后l从maxx开始那就不需要fit函数中这个第一个for的这一行了。
AC代码
#includecstdio
#includequeue
#includecstring
#includecmath
#includeiostream
#includealgorithm
using namespace std;int n,m,sum,l,r;//m个线段最多分成n段、
int a[305];
bool fit(int x) {int cnt 1,cur0;for(int i 1; im; i) if(a[i] x) return 0;for(int i 1; im; i) {if(cura[i] x) cura[i];else cnt,cur0,i--;}if(cnt n) return 0;else return 1;
}
int main()
{int t;cint;while(t--) {sum 0;scanf(%d%d,m,n);for(int i 1; im; i) {scanf(%d,a[i]);sum a[i];}l0,rsum;int mid (lr)/2;while(lr) {mid (l r) / 2;if(fit(mid)) rmid;else lmid1;}printf(%d\n,l);}return 0;
}
