题解 P2678 【跳石头】

· · 题解

【题目大意】给你一排N块石头，你可以移走M块石头，使得最小的两块石头之间的距离尽可能长，N,M≤50000。

【解题说明】

20分做法：直接暴力即可

50分做法：考虑DP，f[i][j]表示在前i块石头移走j块石头的最短距离，转移即可

60分做法：考虑贪心，每次删除间距最小的，用堆维护

100分做法：考虑二分答案后贪心，先二分这个距离使其变为判断可行性问题，然后从前往后扫，一旦这个石头到上一个选的石头的距离小于这个二分的答案就把这块石头移走

这样显然是正确的，很容易证明先移一定比后移好，所以这个算法是正确的

【代码】

#include<cstdio>
int L,n,m,i,w,l,r,mid,pos,ans,a[55555];
bool ok(int x){
    for(pos=w=0,i=1;i<=n;i++)if(a[i]-pos<x)w++;else pos=a[i];
    return w<=m;
}
int main(){
    for(scanf("%d%d%d",&L,&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);a[++n]=L;
    for(l=1,r=L;l<=r;)if(ok(mid=l+r>>1))ans=mid,l=mid+1;else r=mid-1;
    printf("%d",ans);
}
【时间复杂度】 O(nlgL) 【空间复杂度】 O(n) 【思想难度】 30 【编程难度】 23 【总用时】10 min