题解：B4305 [蓝桥杯青少年组省赛 2024] 物品分组

Jayfeather2012 · 2025-04-11 12:37:00 · 题解

思路

一道二分~~
因为各组价值之和的最大值的最小可能值具有单调性，也就是说，如果一个各组价值之和的最大值的上限可以使这些数被分成 k 组，那么小于这个值的上限也可以使这些数被分成 k 组，所以可以考虑二分。
怎么看一个上限最少可以分多少组呢？我们遍历数组，用 s 记录当前分组的和，如果这个值超过上限，就增加要分的组数，并清空 s，随后还要令 s 加上当前遍历的数。
整上二分的板子就 AC 啦！
具体细节看代码吧！

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005];
int check(int x){
    int s=0,ans=0;
    for(int i=1;i<=n;++i){
        if(x<a[i])return 0;
        //如果一个物品价值都比上限大，就一定不符合要求
        s+=a[i];
        //加上当前物品价值
        if(s>x){
            ++ans;
            //增加组数
            s=a[i];
            //s重置为当前物品价值
        }
    }
    ++ans;
    //最后还有一组
    return ans<=k;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    cin>>k;
    int l=1,r=1e8,ans;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    //二分的板子
    cout<<ans<<"\n";
    return 0;
}