本题可以看做是一个数学题
因为 在第 1 和第 3 个洒水器之间的 花园灌溉的时间只要
(1 + 3 ) >> 1 - 1 + 1;
//这么长的时间 那么我么就可以以此类推到从而我么可以进行进一步的推广
例如 有10块土地待浇水 那么就是
1 2 3 4 5 6 7 8 9 10 我们假设 洒水器所处的位置为 3 和 6 那么我们发现 9 / 2 是无法整除的，但是我们可以发现
9 / 2 = 4 很明显 4 是靠近 3 的 所以灌溉 4 的时间就是 4 - 3 +1 秒（因为灌溉③这个位置还需要一秒 而其他的就是 进一步灌溉 最后总共的时间就是 2 秒 所以 我们可以得到如下公式来计算时间(X2 + X1) / 2 - X1 + 1 我们将 3 和 6 代入公式可得 时间为 2但是记住 是
[(X2 + X1) / 2] 是向下取整 没事咱们int自带向下取整然后这就是我们的核心代码 接下来讨论的就是我们算完了 中间的数据后要怎样去 计算不在范围内的土地要多少时间才能被灌溉
从题目可以知道一个非常重要的条件那就是 灌溉器的位置是不断增加的 因此最后一个灌溉器的位置一定是最靠近 最后一块土地的
那么我们就可以初始化得到如下代码假设灌溉器的数组为 q 并且有 k 个灌溉器
int ans = max( q[1] , n - q[k] + 1 )我也不卖关子了
1 #include2 3 using namespace std; 4 5 const int N = 220; 6 int q[N]; 7 int t, n, k; 8 int main() 9 { 10cin >> t; 11while (t--) 12{ 13cin >> n >> k; 14for (int i = 1; i <= k; i++) cin >> q[i]; 15 16int res = max(q[1], n - q[k] + 1); 17 18for (int i = 1; i < k; i++) 19res = max(res, ((q[i] + q[i + 1]) >> 1) + 1 - q[i]); 20cout << res << endl; 21} 22return 0; 23 }
【CF|CF 920A Water The Garden】
