第4点 wa 求助

P1182 数列分段 Section II

shy111 @ 2024-04-02 22:46:33

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
long long n,m;
long long a[10*N];
bool check(long long mid){
    long long num=1,sum=0;
    for(int i=1;i<=n;i++){
        if(sum+a[i]<=mid){
            sum+=a[i];
        }
        else{
            num++;
            sum=a[i];
        }
    }
    //cout<<num<<endl;
    if(num>m){
        return 0;
    }
    else if(num<=m){
        return 1;
    }
}
long long erfen1(){
    long long l=1;
    long long r=0x3f3f3f3f3f3f3f3f;
    while(l<r){
        long long mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return r;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    long long ans;
    ans=erfen1();
    cout<<ans;
    return 0;
}

求助各位大佬


by 1____1 @ 2024-04-02 22:49:09

你应该用max函数而不是加上a[i]


by shy111 @ 2024-04-02 22:53:32

@1____1 好,但我不知道在哪个地方呢?


by Frederick12321 @ 2024-04-09 00:36:55

你在check函数中,else那里加a[i]的时候要特判一下,如果a[i]>mid,直接return false


by shy111 @ 2024-04-09 11:34:43

@Frederick12321 ac了,非常感谢!


|