T683041 题解

30pts：

纯送分。

直接暴力枚举

i,j

并暴力计算

[i,j]

区间的和，时间复杂度

O(n^3)

。

CPP

#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 以后，就可以轻松解决了。

代码：

CPP

#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 轻松过题。

文章操作

相关推荐

评论

T683041 题解