T683041 题解

zhujianheng · 2025-10-21 22:17:12 · 个人记录

30pts：

纯送分。

直接暴力枚举 i,j 并暴力计算 [i,j] 区间的和，时间复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=500009;
ll a[N],s[N],n,m,ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    for(ll i=1;i<=n;i++)
        for(ll j=i;j<=n;j++){
            ll s=0;
            for(ll k=i;k<=j;k++) s+=a[k];
            ans+=(s<=m);
        }
    cout<<ans<<endl;
    return 0;
}

但实际上这份代码可以获得 50pts，甚至能 n^3 过 n=2543 的一个点。（966ms）

但有一组数据我造的比较大，大概 n=3700，于是我就没有放过 60pts。

60pts（测过，严格 60pts）：

考虑用前缀和优化这一过程。直接把一段区间的和转化为 s_i-s_{j-1}，时间复杂度 O(n^2)。

100pts：

考虑转化 s_i-s_{j-1} \le m，变成 s_i \le s_{j-1}+m，然后枚举 j，因为全部是正整数，二分 s_i，求出 lower_bound 以后，就可以轻松解决了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=500009;
ll a[N],s[N],n,m,ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    for(ll i=1;i<=n;i++){
        ll j=lower_bound(s+1,s+1+n,s[i]+m)-(s+1);
        ans+=(j-i+1);
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度 O(n \log n)，跑的挺快，40ms 轻松过题。