NTHU OJ - 2706 The Frog's Games (HDU 4004)

The following program is my ACcepted code for NTHU-2706 .
It's a for everybody to learn and discuss.
If there is any mistake or comment, please let me know.  :D

此乃NTHU 2706 的AC code!

歡迎一同討論學習，如有錯誤與任何建議請留言 : )

點這裡看題目 Click here to see this Problem! (NTHU 2706 中文題目)

點這裡看題目 Click here to see this Problem! (HDU    4004 英文題目)


//This program is for NTHU 2706 The Frog's Games (HDU 4004)
//NTHU (中文)題目來源 Problem link: http://acm.cs.nthu.edu.tw/problem.php?pid=7206
//HDU    (英文)題目來源 Problem link: http://acm.hdu.edu.cn/showproblem.php?pid=4004

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define MAX 500000
using namespace std;

int L, N, M;
int n[MAX], d[MAX];

bool canbe(int jump)
{
    int count = 0;//number of jumping
   
    //if one jump is larger than previous rock, this variable is the left distance
    int left = 0;
   
    for(int i = 0; i <= N; i++)
    {
        if(count > M)//over the Maximun steps frog can take
            return false;
       
        if(left >= d[i])
        {
            left -= d[i];
            continue;//use the left to next rock
        }
       
        left = 0;//a new jump!
       
        if(jump < d[i])
            return false;
       
        if(jump >= d[i])
        {
            count ++;
            left = jump - d[i];
        }
    }
    if(count > M)
        return false;
       
    return true;
}

int findMin()//binary search for the ans
{
    int beg, end, mid;
   
    beg = 1;
    end = L;
   
    do{
        mid = (beg + end) / 2;
        if(canbe(mid))
            end = mid;
        else
            beg = mid + 1;
        //printf("beg: %d   end: %d\n", beg, end);
    }while(beg < end);
   
    return end;
}

int main()
{
    while(scanf("%d %d %d", &L, &N, &M) != EOF)
    {
        for(int i = 1; i <= N; i++)
            scanf("%d", &n[i]);//n[] are the places of rocks
       
        sort(n + 1, n + N + 1);
       
        d[0] = n[1];
        for(int i = 1; i< N; i++)
            d[i] = n[i + 1] - n[i];//d[] are the distances between rocks or banks
        d[N] = L - n[N];

        printf("%d\n", findMin());
    }
    return 0;
}

Please feel free to use it after adding this blog as an reference. (http://autekroy.blogspot.tw) If there is any mistake or comment, please let me know. :D 

歡迎使用與分享任何內容，但請記得標示此部落格為出處。(http://autekroy.blogspot.tw/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )