飞机票：http://codeforces.com/contest/551/problem/C

题意：有一个数组ai[]，有n个元素，ai[i]代表第i个元素的值，有m个学生，学生在最左边，且到第i个元素要i秒，且使第i个元素值减1需要花费1秒，求m个人使所有值为0最少要多少时间，学生可以同时行动。

分析：题目一看，必然二分啊，但是怎么维护这个值呢？这里有2种方法，假设当前判断的值是mid

(1)从后往前推：假设最右边不为0的下标为k，则学生到k需要花费k秒，如果mid<=k直接就不行，因为到了k这个点就没时间了。所以mid肯定要大于k，然后ai[k]就要减掉mid-k的值，这样就是最优的，因为学生的时间没有一秒浪费。

(2)从前往后推：这个情况有点难理解，只能YY了，假设当前的人在i,且后面有值的地方在j（i<j）,如果当前这个人再拿一个i的值，他到不了j或则到了j已经没有时间了，这样就有时间浪费了，但是我们会发现，下个人他就多了1秒的时间，就是他如果能到j，则他可以多拿一个，并不会影响到最优值。有点难理解哇~

我的代码是用第二种方法的，复杂度为O（log2INF*n）INF=2*1e18，要及时跳出循环，不然就TLE了，啪啪啪，就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#define LL long long
#define INF 1e20
#define EPS 1e-9
using namespace std;
const int maxn=123456;
LL ai[maxn];
LL bi[maxn];
int n,m;
void init()
{

    for(int i=1; i<=n; i++)
    {
        scanf("%I64d",&ai[i]);
        bi[i]=ai[i];

    }
}
void play()
{
    LL l=0;
    LL r=INF;
    LL ans=r;
    LL p=INF;
    for(int i=n; i>=1; i--)
    {
        if(ai[i]>0)
        {
            p=i;
            break;
        }
    }
    if(p==INF)
    {
        printf("0\n");
        return;
    }
    n=p;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        int st=1;
        for(int i=1; i<=m; i++)
        {
            LL t=mid;
            int ti=st;
            for(int j=st; j<=n; j++)
            {
                LL now=ai[j]+ti;
                if(now>t)
                {
                    st=j;
                    t-=ti;
                    if(t>0)
                    {
                        ai[j]-=t;
                    }
                    break;
                }
                else
                {
                    t-=now;
                    ai[j]=0;
                    ti=1;
                    st=j;
                }
            }
            if(st==n&&ai[n]<=0)break;
        }
        bool flag=0;
        if(st==n&&ai[n]<=0)flag=1;
        LL p=ai[n];
        for(int i=1; i<=n; i++)ai[i]=bi[i];
        if(!flag)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
            ans=mid;
        }
    }
    printf("%I64d\n",ans);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}