UVA11413 题解

getchar_unlocked · 2025-02-19 22:03:54 · 题解

题目传送门

思路

发现题目具有单调性，考虑二分。

可以二分最大容器的容量。对于容量是否合法的判断，可以模拟装容器的过程，并统计子序列数是否 >M 即可。

注意事项

• 控制好二分上下界（下界为 \max\{A_i\}，上界为 \sum A_i）。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10;
int n,m,a[N];
bool check(int x){
    int sum=0,res=1;
    for(int i=1;i<=n;++i){
        sum+=a[i];
        if(sum>x){
            sum=a[i];
            ++res;
        }
    }
    return res>m;
}
signed main(){
    while(scanf("%lld%lld",&n,&m)!=EOF){
        int l=0,r=0;
        for(int i=1;i<=n;++i){
            a[i]=read();
            l=max(l,a[i]);
            r+=a[i];
        }
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid))
                l=mid+1;
            else r=mid-1;
        }
        printf("%lld\n",l);
    }
    return 0;
}