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

No_coding_extra · 2025-04-12 21:58:01 · 题解

题目大意：

题目传送门

本蒟蒻建议先做这道题，这道题比较基础，思路也很相似。

题目思路：

这还用说吗？肯定是二分答案呀！

模板：

while(l<=r){
  int mid=l+r>>1;
  if(check(mid)) r=mid-1;
  else l=mid+1;
}

这道题的重点是判断函数，如果这个物品的价值已经 > 现在的答案了，就无法装下，那就应该调整答案了。如果这个物品的价值 + 目前包里的总价值 \le 现在的答案，那就装进去。否则就新开一个袋子，并把当前的物品装进去。

思路讲的很清晰，上代码吧！

正解：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[1005],s,l,r;
bool check(int x){
    int ans=0,cnt=1;
    for(int i=1;i<=n;i++){
        if(x<a[i]) return false;
        if(ans+a[i]<=x) ans+=a[i];
        else{
            cnt++;
            ans=a[i];
        }
    }
    return cnt<=k;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int o=INT_MAX;
    for(int i=1;i<=n;i++) cin>>a[i],s+=a[i],o=min(o,a[i]);
    cin>>k;
    l=o,r=s;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<"\n";
    return 0;
}

懂了就给个赞！