2019年第十屆藍(lán)橋杯 - 省賽 - C/C++研究生組 - G. 掃地機(jī)器人

Ideas

首先我們根據(jù)數(shù)學(xué)常識(shí)可以知道，當(dāng)每個(gè)機(jī)器人清掃的范圍差不多時(shí)，最好都是 N / K，花的時(shí)間應(yīng)該是最少的。

所以這道題實(shí)際上就是讓我們搜索每個(gè)機(jī)器人負(fù)責(zé)清掃的范圍，我們假設(shè)這個(gè)范圍是x。

既然是搜索，那么首先想到的就是二分，不斷的縮小x的過(guò)程中確保所有機(jī)器人的清掃范圍能夠覆蓋N個(gè)方格。

二分不是很麻煩，所以重點(diǎn)是確保所有機(jī)器人的清掃范圍能夠覆蓋N個(gè)方格。

給定一個(gè)x之后，我們可以遍歷每個(gè)機(jī)器人所在的位置依次判斷，因?yàn)轭}目中給出的機(jī)器人的位置并不是有序的，所以讀入數(shù)據(jù)之后還要先排序。

我們可以設(shè)置一個(gè) total 變量，表示從左到右依次能夠清掃的范圍。

對(duì)于每一個(gè)機(jī)器人所在的位置k[i]，如果k[i] - x，也就是機(jī)器人能夠清掃的左邊界小于total的話(huà)，分成兩種情況：

k[i] < total: 說(shuō)明前面一個(gè)機(jī)器人k[i - 1]能夠清掃的右邊界達(dá)到k[i]的起始位置，那么第i個(gè)機(jī)器人就不用往左邊走了，此時(shí)前i個(gè)機(jī)器人能夠清掃的total = k[i] + x - 1；

k[i] >= total: 說(shuō)明前面一個(gè)機(jī)器人k[i - 1]能夠清掃的右邊界沒(méi)有達(dá)到k[i]的起始位置，那么第i個(gè)機(jī)器人就需要往左邊清掃，而此時(shí)前i個(gè)機(jī)器人能夠清掃的total = total + x；

如果 k[i] - x > total 的話(huà)，也就是第 i 個(gè)機(jī)器人能夠清掃的左邊界都大于前 i - 1 個(gè)機(jī)器人能夠清掃到的范圍，那說(shuō)明這個(gè) x 選的太小了，得增大范圍。

最后找到了合適的 x 之后，那么花費(fèi)時(shí)間最長(zhǎng)的機(jī)器人，就是這個(gè)機(jī)器人的位置正好在 x 的中間，它需要先往左掃，再回來(lái)，然后往右掃，再回來(lái)，所以花費(fèi)的最長(zhǎng)時(shí)間為 (x - 1) * 2。

然后我們就可以開(kāi)始寫(xiě)代碼啦。

Code

C++

#include <iostream> #include <algorithm>using namespace std;const int maxn = 1e5+7; int n, m; int robot_list[maxn];bool check(int x) {int total = 0;for (int i = 0; i < m; i++) {if (robot_list[i] - x < total + 1) {if (robot_list[i] < total + 1) {total = robot_list[i] + x - 1;} else {total += x;}} else {return false;}}return total > n - 1; }int main() {cin >> n >> m;for (int i = 0; i < m; i++) {cin >> robot_list[i];}sort(robot_list, robot_list + m); int left = 0, right = n, middle, ans;while (left < right + 1) {middle = (right + left) >> 1;if (check(middle)) {right = middle - 1;ans = middle;} else {left = middle + 1;}}cout << (ans - 1) * 2 << endl;return 0; }

Python

def check(x):total = 0 # 前面的機(jī)器人能夠清掃的右邊界，初始化為0for i, v in enumerate(robot_list):if v - x < total + 1:if v < total + 1:total = v + x - 1else:total += xelse:return Falsereturn total > n - 1if __name__ == '__main__':# 1. 處理輸入數(shù)據(jù)n, k = map(int, input().split())robot_list = []for _ in range(k):robot_list.append(int(input()))robot_list.sort()# 2. 二分查找left, right, ans = 0, n, nwhile left < right + 1:middle = (right + left) >> 1if check(middle): # 如果此時(shí)確定的清掃范圍可以滿(mǎn)足條件則繼續(xù)縮小范圍ans = middleright = middle - 1else:left = middle + 1print((ans - 1) * 2)

在線(xiàn)評(píng)測(cè)：https://www.acwing.com/problem/content/3179/

總結(jié)

以上是生活随笔為你收集整理的2019年第十届蓝桥杯 - 省赛 - C/C++研究生组 - G. 扫地机器人的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。