跳石头1890

int l,n,m;

int a[100000];

bool f(int mid){

   int s=0;

   int c=0;

   for(int i=1;i<=n;i++){

       if(a[i]-s<mid) c++;

       else s=a[i];

   }

   return c<=m;

}

int main(){

   cin>>l>>n>>m;

   for(int i=1;i<=n;i++){

       cin>>a[i];

   }

   a[++n]=l;

   //二分法：最短跳跃的最大距离

   int left=1,right=l;

   while(left<right){

       int mid=(left+right)/2;

       if(f(mid)){

           left=mid;

       }

       else{

           right=mid-1;

       }

   }

   cout<<left;

   return 0;

}

快速排序

sort的核心原理

void qsort(int left,int right){

   if(left==right) return ;

   int bb=a[left];

   int s1=left,s2=right;

   while(s1<s2){

       while(a[s2]>=bb&&s1!=s2) s2--;

       while(a[s1]<=bb&&s1!=s2) s1++;

       swap(a[s1],a[s2]);

   }

   swap(a[left],a[s1]);

   qsort(left,s1-1);

   qsort(s1+1,right);

}

int main(){

   int a[9]={6,7,3,1,8,2,9,5,4};

   qsort(0,8);

}

快速排序，是综合排序最快的算法

快速排序的快慢，与标兵的取值有关，恰好中值就很快，恰好边界就很慢

1242 网线主管

时空复杂度