二分+并查集

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

/*

其实这一题自己最大的收获是数学等价，来回跳2x次等价于单向跳2x次，证明：

假设可以来回跳2x次，那么按回来的跳的石头正着跳就行，=>可以单向跳2x次

假设可以单向跳2x次，那么从对岸按偶数次的跳的石头来跳就行=>可以来回跳2x次

所以可以来回跳2x次<=>可以单向跳2x次

这道题自己暴力的算法70分，时间复杂度为O(logn*(n+x*n))=O(logn*n*x)

优化：

1.使用了并查集;2.改变了一个青蛙一个青蛙跳的思想，而是一起跳;时间复杂度为O(n*logn),new online judge能得100分

*/

using namespace std;

#define maxn 100010

#define maxx 1e9+10

int n,x;//n是河的宽度，x是天数,显然石头数为n-1

int pare[maxn];

int h[maxn],tmph[maxn];

int fnum[maxn];//记录每块石头上的青蛙数

int findroot(int a){

    if(a!=pare[a]){

        pare[a]=findroot(pare[a]);//压缩路径

    }

    return pare[a];

}

void Union(int x,int y){

    y=findroot(y);

    x=findroot(x);

    pare[y]=x;//以x为根

}

bool isok(int abi){//ability

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

        tmph[i]=h[i];

    }

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

        pare[i]=i;

    }

    memset(fnum,0,sizeof(fnum));

    fnum[0]=x;//出发处有x只青蛙

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

        if(i+abi>=n){

            return 1;//所有青蛙都能到对岸

        }

        while(fnum[i]){//一直跳到前i块石头没有青蛙，也就是第i块石头没有青蛙，因为i是从0开始循环的

            int root=findroot(i+abi);

            if(root<=i)return 0;//已经没有能跳的石头

            int jumpnum=min(tmph[root],fnum[i]);

            fnum[i]-=jumpnum;

            tmph[root]-=jumpnum;//跳上去就高度下降和跳走后高度下降本质上一样，高度都表示了这个石头的承载量

            fnum[root]+=jumpnum;

            if(!tmph[root]){

                pare[root]=findroot(root-1);//Union

            }

        }

    }

    /* for(int i=1;i<=x;i++){

        int pos=0;

        int minpos=0;

        while(pos<n){//当还没到终点时

            int flag=0;

            int tmp=pos;

            for(int j=pos+abi;j>minpos;j--){

                if(j>=n||tmph[j]){

                    tmph[pos]--;

                    pos=j;

                    flag=1;

                    break;

                }

            }

            minpos=tmp+abi;//小于minpos的地方不会跳到，这就是一种去重

            if(!flag){//没有成功往前跳

                return 0;

            }

        }

    }

    return 1;*/

}

int findmin(int l,int r){//寻找最小的满足条件的跳跃能力,每个区间必然有至少一个满足条件

    if(l==r)return l;//找到了答案

    int mid=l+((r-l)>>1);//完全等价于mid=(l+r)/2,自己找几个例子验证就明白了

    if(isok(mid))return findmin(l,mid);

    else return findmin(mid+1,r);

}

int main(){

    scanf("%d%d",&n,&x);

    x=x<<1;

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

        scanf("%d",&h[i]);

    }

    printf("%d\n",findmin(1,n));

    system("pause");

    return 0;

}