2020-09-14 跳石头

https://www.luogu.com.cn/problem/P2678

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

//template<typename DataType>
//DataType qmi(DataType m, int k)
//{
//    DataType res = 1, t = m;
//    while (k)
//    {
//        if (k&1) res = res * t;
//        t = t * t;
//        k >>= 1;
//    }
//    return res;
//}


int qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

#define fi(a,b) for(int i = a; i <= b; i++)
#define fj(a,b) for(int j = a; j >= b; j--)

struct priceAndCnt{
    int price,cnt;
};

void quickSort(priceAndCnt *a,int left,int right){
    int i,j;
    
    priceAndCnt temp,t;
    
    temp = a[(left+right)/2];//基准值
    
    i = left;
    j = right;
    
    while(i<=j){
        while (a[j].price > temp.price) {
            j--;
        }
        
        while (a[i].price < temp.price) {
            i++;
        }
        
        if (i<=j) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            //继续下一步
            i++;
            j--;
        }
    }
    
    if(left<j)quickSort(a,left, j);//继续分治
    if(i<right)quickSort(a,i, right);//继续分治
}


int L,N,M;
int arr[50000];

bool judge(int x){//judge函数，x代表当前二分出来的答案
    int tot = 0;//tot代表计数器，记录以当前答案需要移走的实际石头数
    int i = 0;//i代表下一块石头的编号
    int now = 0;//now代表模拟跳石头的人当前在什么位置
    while (i < N+1){//千万注意不是n，n不是终点，n+1才是
        i++;
        if (arr[i] - arr[now] < x)//判断距离，看二者之间的距离算差值就好
            tot++;//判定成功，把这块石头拿走，继续考虑下一块石头
        else
            now = i;//判定失败，这块石头不用拿走，我们就跳过去，再考虑下一块
    }
    if (tot > M)
        return false;
    else
        return true;
}

int main()
{
    L = read();
    N = read();
    M = read();
    
    fi(1, N){
        arr[i] = read();
    }
    
    arr[ N+1 ] = L;//敲黑板划重点，再强调一遍，n不是终点
    int l = 1;//l和r分别代表二分的左边界和右边界
    int r = L;
    int ans = 0;
    while (l <= r){//非递归式二分正常向写法，可理解为一般框架
        int mid = (l + r) / 2;//这再看不出是啥意思可以退群了
        if ( judge(mid) ){//带入judge函数判断当前解是不是可行解
            ans = mid;
            l = mid + 1;//走到这里，看来是可行解，我们尝试看看是不是有更好的可行解
        }
        else
            r = mid - 1;//噫，你找了个非法解，赶紧回到左半边看看有没有可行解
    }
    cout << ans << endl;//最后的ans绝对是最优解
    return 0;
}
/*
3 7
232
124
456
============
114
*/