二分+贪心 || CodeForces 551C GukiZ hates Boxes

N堆石头排成一列，每堆有Ai个石子。有M个学生来将所有石头搬走。一开始所有学生都在原点，每秒钟每个学生都可以在原地搬走一块石头，或者向前移动一格距离，求搬走所有石头的最短时间。

*解法：二分答案x（时间），即每位学生均有x秒的时间，模拟搬石头过程看能否搬完即可（一个人一个人计算，每个人均尽力完成任务即可）。

记得开longlong

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

#define SZ 100005

#define INF 1e15+10

long long a[SZ], b[SZ];

int n, m;

int check(long long x)

{

    int flag = ;

    long long p = , t;//时间x

    for(int i = ; i <= n; i++) b[i] = a[i];

    for(int i = ; i <= m; i++)

    {

        t = x - p;

        while(t >  && p <= n)

        {

            if(t > b[p]) {t -= b[p]; b[p] = ; p++; t--;}

                //do{p++; t--;} while(b[p] == 0);

            else if(t == b[p]) {b[p] = ; p++; t = ;}

            else {b[p] -= t; t = ;}

        }

    }

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

        if(b[i] > ) flag = ;

    if(!flag) return ;

    return ;

}

int main()

{

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

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

        scanf("%lld", &a[i]);

    long long l = , r = INF, mid;

    while(r > l)

    {

        mid = (r + l) / ;

        if(check(mid)) r = mid;

        else l = mid + ;

    }

    printf("%lld\n", r);

    return ;

}

巴特西

二分+贪心 || CodeForces 551C GukiZ hates Boxes

最新文章

热门文章