AcWing 3176. 扫地机器人
原题链接
简单
作者:
Mr.W
,
2021-01-19 21:13:33
,
所有人可见
,
阅读 1002
#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int a[100005];
// l 左边界 Q 区间大小
bool f(int l, int Q)
{
for(int i = 0; i < k; i ++ )
if(a[i] - Q <= l) // 若当前机器人的下标减去区间大小 <= 左边界的时候 说明可以继续 否则退出
{
if(a[i] <= l) l = a[i] + Q -1; // 若机器人 在左边界内 边界就该等于机器人向右所能扫到的最远点
else l = a[i] + Q - (a[i] - l );
}
else
return false;
if(l < n) return false; // 遍历完机器人 若左边界小于 n 则说明没有全部清扫
return true;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < k; i ++ )
scanf("%d",&a[i]);
sort(a, a + k);
int Q; // 区间大小
Q = (n / k) >= a[0] ? n / k : a[0]; // 区间初始化 最小可能的区间
for(; Q <= n; Q ++ )
{
int l = 0; // 左边界 初始为 0
if(f(l, Q)) break;
}
cout << 2 * (Q - 1) << endl; // 步数 = (区间大小 - 1) * 2
return 0;
}
else l = a[i] + Q - (a[i] - l ); 为什么还要减去 a[I]-I
不应该是。l=a[i]+q 吗
if(a[i] <= l) l = a[i] + Q -1;
这里为什么要减1很明显呀,$a[i] + Q$ 作为 $r$ 的话,$l$ ~ $r$ 区间的大小就不是 $Q$ 了,所以要 - $1$。