实验七 数组(二) |
您所在的位置:网站首页 › 冬天到了没 › 实验七 数组(二) |
实验七 数组(二)---松雅的花园
0、题目概述【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】【样例说明】【评分标准】
1、分析2、解决方案3、代码4、总结
0、题目概述
【问题描述】
冬天到了,松雅觉得是时候给她的花园浇水了。 她的花园由 n 个连续的苗圃组成,编号从 1~n。其中的 k 个苗圃安装有水龙头(第 i 个水龙头位于苗圃 xi),当水龙头打开的时候,可以同时给相邻的苗圃浇水。1个时间单位后,她可以给苗圃 xi 浇好水,2个时间单位后,她可以给 [xi-1, xi+1] 范围内的苗圃(如果有)浇好水,在 j 个时间单位后,她可以给[xi-(j-1),xi+(j-1)]内的苗圃(如果有)浇好水。
第一行一个整数表示测试数据的组数。 接下来T组测试数据 ,每组数据的第一行包含两个整数 n 和 k,分别表示她的花园中的苗圃数和水龙头数,接下来的一行为 k 个整数 xi,表示第 i 个水龙头所在的位置,输入保证对于每个 i >=2,xi - 1 < xi 。 本题只考虑整数单位时间。 【输出形式】对于每个测试用例,每个用例输出一行一个整数,表示所有水龙头同时打开后整个花园浇好水所需要的最小时间单位数。 【样例输入】3 5 1 3 3 3 1 2 3 4 1 1 【样例输出】3 1 4 【样例说明】 【评分标准】 1、分析这一道题对于大一的初学者(或者c++的初学者)来说,稍微有些难度。刚拿到题目可能会选择用数组存入水龙头的位置,再进行机器模拟。其实没有那么复杂,这里提供一种相对简单的思路: 我们关注的是花园全部浇水的情况,所以只需要关注“等效距离”最大即可。 这里的等效距离指的是:灌溉完这段距离需要的时间。因为两端和中间的计算公式不一样。 2、解决方案空地有两类,一类是两端均有水龙头,另一类是只有一段有水龙头。 对于第一类:等效时间是两个水龙头之间的距离除以2(小数进一)。这一类地,两端都有水龙头,所以被灌溉的速度是两端的两倍。 对于地而来:水龙头到边界的距离(边界为0和n+1) 3、代码 #include //为避免学校oj系统查抄袭,所有字母在使用时请进行修改 using namespace std; int main() { int T; cin>>T; for (int jishu=1; jishu>N1>>K1; int sum111=0; cin>>A1; //这里为了省略一个二维数组,采用了每次只读相邻两个数的方法。 sum111=A1; B1=A1; for (int I=2; I>B1; //下面的两个判断,均只储存最大的值 if (((B1-A1+1)%2==0)&&((B1-A1+1)/2>sum111)) sum111=(B1-A1+1)/2;//两个水龙头之间的距离是奇数 else if (((B1-A1+1)%2==1)&&((B1-A1+1)/2+1>sum111)) sum111=(B1-A1+1)/2+1;//两个水龙头之间的距离是偶数 A1=B1;//将这一次的后一个水龙头变成下一次的前一个 } if (N1-B1+1>sum111) sum111=N1-B1+1;//特判最后一个水龙头到最末端 cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |