这是一道二分，和贪心题，这种题往往二分简单，但是如何进行check 也就是贪心的证明是最难的。
题目要求最少花费时间。由于每个机器人的工作时间可能不同，那么这些机器人各自的花费时间中的最大值（设为t） 的就是本题要求的答案，需要做的是让t最小，将最大花费时间t最小化，显然需要使用二分求解。
假设某个机器人需要清扫abcd四个格子，因为这个机器人清扫玩还需要回到最初的位置，所以无论这个机器人初始位置在什么地方，其清扫路径的本质都是重复两个a到b，b到c，c到d的过程，花费时间为6，由此，假设有个机器人清扫的格子范围为l。那么这个机器人花费的时间（l-1）*2；
显然当每个机器人清扫的范围大小相同时，花费时间最小，可以对清扫范围进行二分，然后验证其答案的正确性即可，判断条件是清扫范围可以使得每个格子都能够扫到；
可以明显的知道，最左边的格子由最左边的第一台机器人清扫，花费时间是最少的，再次可以用贪心的思想。
让每一台机器人都要优先清扫其左边还未扫的格子，然后再往右扫，在二分的到的范围下往右扫的越多越好。这样可以减少右边下一个机器人需要左扫的范围，增加其往右扫的范围。
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std ; const int N = 1e5+10 ; int n , m ; int r[N] ;//机器人 bool check(int len){ int pos = 0 ; for(int i = 1 ; i <= m; i ++){ if(r[i] - len <= pos ){//如果当前机器人往左扫的个数可以到达当前清扫到的位置pos if(r[i] <= pos) pos = r[i] + len -1 ;//如果当前清扫完的点在机器人右边，那直接用当前机器人的位置更新pos清扫点的位置即可 else pos += len ;//在左边，那就直接加当前机器人能清扫的格子数 }else {//中间有清扫不到的，直接返回false return 0 ; } } return pos >= n ; } int main(){ cin >> n >> m ; for(int i = 1 ; i <= m ; i ++){ cin >> r[i] ; } sort(r+1,r+1+m) ;//因为不是顺序输入，所以要先排序 int l = 0 , r = n ; while(l < r){//二分所能打扫的方格个数 int mid = r + l >> 1 ; if(check(mid))r = mid ; else l = mid + 1 ; } cout << (l-1) *2 << endl ; }
