CF 920A Water The Garden

• 2022 年 3 月 26 日
• 筆記
• CF

本題可以看做是一個數學題

因為 在第 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 )

我也不賣關子了 接下來就是 AC程式碼了

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 const int N = 220;
 6 int q[N];
 7 int t, n, k;
 8 int main()
 9 {
10     cin >> t;
11     while (t--)
12     {
13         cin >> n >> k;
14         for (int i = 1; i <= k; i++) cin >> q[i];
15 
16         int res = max(q[1], n - q[k] + 1);
17 
18         for (int i = 1; i < k; i++)
19             res = max(res, ((q[i] + q[i + 1]) >> 1) + 1 - q[i]);
20         cout << res << endl;
21     }
22     return 0;
23 }