自动搬运

查看原文

来自洛谷，原作者为

	CCY20130127 你我本来无缘，纯靠coding相伴

搬运于2025-08-24 21:18:30，当前版本为作者最后更新于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;
}

懂了就给个赞！