3 solutions

  • 1
    @ 2022-6-6 20:23:07

    关于二分的一点心得: 二分分出来的大多时候都是答案,所以我们要按照这个思路去找 比如这题,一开始我上来就想对石头二分,当然我们知道这是不 可能对的,二分需要check,按石头二分显然难以找到check。 后来看了下别人的代码,发现二分的就是答案,即距离x。所以拿 到一道二分题可以先看看答案是啥,凭着这个思路去找check,就 很简单了。(会不会大佬早就知道了,只有我现在才发现)

    #include<iostream>
    using namespace std;
    
    int stone[50007];
    int n,m,l;
    
    int check(int x){
    	int cns=0;
    	int now=0;
    	for(int i=1;i<=n;i++){
    		if(stone[i]-stone[now]<x){
    			cns++;
    			if(cns>m){
    				return false;
    			}
    		}
    		else now=i;
    	}
    	return true;
    }
    
    int search(int l,int r){
    	int mid;
    	while(l<=r){
    		mid=(l+r+1)>>1;
    		if(!check(mid))r=mid-1;
    		else l=mid+1;
    	}
    	return l-1;
    }
    
    
    int main(){
    	cin>>l>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>stone[i];
    	}
    	cout<<search(0,l);
    	return 0;
    }
    

    Information

    ID
    252
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    4
    Tags
    # Submissions
    236
    Accepted
    47
    Uploaded By