扫地机器人 二分答案,贪心 蓝桥杯

二分答案 与二分查找类似，二分查找有一个前提就是数列要求是有序的，二分答案则是要求 满足条件的答案是单调有序的，它的基本思想是在答案可能的范围 ([L,R]) 内二分查找答案，不断检查当前答案是否满足题目的要求，根据检查结果更新查找的区间，最终取得最符合题目要求的答案进行输出。

模板：

ans和left一起是最大值

ans和right一起是最小值

这个mid相当于答案，用check函数去检查他是否可行

例题：

一个程序10的8次方是运行一秒，二分还有sort(快速排序)都是nlog(n)

对于包含大量重复元素的数组，快速排序的时间复杂度会退化至 O(N2)

、#include<bits/stdc++.h>
using namespace std;
int i,n,a[100009],k,ans=0;
bool check(int mid){
  int pos=0,t;//pos前面清扫过的位置
  for(i=0;i<k;i++)
  {  //已经清扫的位置还没到当前机器人的位置a[i]
  //一个位置机器人是要去回，一个格子消耗两个时间 
         t=mid;//贪心，每个机器人都花费这些时间 
    if(pos<a[i]) t=t-(a[i]-pos-1)*2;//当前机器人前面清扫掉
    if(t<0) return false;//不能返回到出发格 
    int qs=t/2;//剩下的t能清扫的 
    pos=a[i]+qs; 
  }
  if(pos<n) return false;
  return true;  }
int main(){
   cin>>n>>k;
   for(i=0;i<k;i++)
   cin>>a[i];
   sort(a,a+k);//mid就是机器人清扫花费的时间 ，贪心算，这个机器人扫这些的同时
//其他机器能否花小于等于他的时间，然后所有的地也被清洁完 ,check的时候按所有机器都清扫mid算 
   //check时 是从头算，是否清洁完在这个走廊 
   int left=0,right=n*2,mid;
   while(left<=right){
    mid=(right+left)/2;
    if(check(mid)){
      ans=mid;
    right=mid-1;//当前mid可以，然后要去寻找更加符合的，就是更小的 
     }
     else
     left=mid+1;
   }
   cout<<ans;
return 0;
 }