暴力模拟 - P7798

· · 题解

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

一开始做这题没看数据范围搞了个 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 就必须要这样做了。