自动搬运

查看原文

来自洛谷，原作者为

	超级玛丽王子 AFO

搬运于2025-08-24 22:33:11，当前版本为作者最后更新于2021-08-11 14:13:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题目教会了我们什么呢？学会看数据范围

一开始做这题没看数据范围搞了个 $O(N\log N)$ 的二分做法（后面会简单讲），写完才发现数据范围写的清清楚楚：$N\le10^3$。

于是依照题意乖乖的写 $O(N^2)$。开一个数组记录“饱食度”，并枚举起点。依照题意找出对应的终点，算出能吃到的果子数量。最后算出每一次吃到的果子数量中的最大值即可。

粗略计算：这个算法的复杂度在最坏情况下是 $O\left(\dfrac{N(N+1)}{2}\right)=O(N^2)$，最优情况是 $O(N)$。均摊一下可能是 $O(N\log N)$ 或者 $O(N\sqrt N)$ 之类的，根本不需要二分（枯了）（

代码：

#include <bits/stdc++.h>
using namespace std;
int n,c,w[1050];
int ans,cur,curr; 
int main(void) {
	cin>>n>>c;
	for(int i=0;i<n;++i) cin>>w[i];
	for(int st=0;st<n;++st) {
		cur=curr=0;
		for(int pos=st;pos<n;++pos) {
			if(curr+w[pos]<=c) cur++,curr+=w[pos];
		}
		ans=max(ans,cur);
	}
	cout<<ans<<endl;
}

至于二分的做法是维护一个前缀和，枚举起点，然后在前缀和上二分查找相应的终点。这个做法是稳定的 $O(N\log N)$，如果数据开到 $10^6$ 就必须要这样做了。