问题标题: 酷町堂：7092 载重(load)

7092   载重(load)

经验值：2000 时间限制：500毫秒 内存限制：128MB

庐阳区2021年信息学竞赛试题

 不许抄袭，一旦发现，直接清空经验！

题目描述 De**ion

某星球发生**难，他们需要乘坐飞船逃离该星球。该星球有N个居民，已经排好队，要求按照队伍的顺序登船。飞船只能飞行M趟，为了控制成本，需要将飞船的承重设计的尽可能的小，给定N个居民的体重，求飞船的承重。

输入描述 Input De**ion

第一行两个整数N和M，意义如题所述
第二行，N个整数，表示居民的体重

输出描述 Output De**ion

一个整数，意义如题所述

样例输入 Sample Input

8 3 40 30 50 80 100 120 40 60

样例输出 Sample Output

220

数据范围及提示 Data Size & Hint

1<=N<=1000000
1<=M<=100000

王选在2023-03-17 17:56:16追加了内容

#include<iostream>

#include<cmath>

#include<cstdio>

using namespace std;

long long n,mins;

long long a[100005],l=1,r,m;

bool judge(int x)

{

    long long ans=1,cnt=0;

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

    {

        if(cnt+a[i]<=x)

        {

            cnt+=a[i];

        }

        else

        {

            if(a[i]>x)

            {

                return false;

            }

            ans++;

            cnt=a[i];

        }

    }

    if(ans<=m)

    {

        return true;

    }

    return false;

}

int main()

{

    cin>>n>>m;

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

    {

        cin>>a[i];

        r+=a[i];

    }

mins=r;

    while(l<r)

    {

        long long mid=(l+r)/2;

        if(!judge(mid))

        {

            l=mid+1;

        }

        else

        {

            mins=min(mins,mid);

            r=mid;

        }

    }

    cout<<mins;

    return 0;

}

Wrong Answer：60分