当前位置: 首页> 科技> 名企 > 如何制作自己的网站 可放广告_网页界面设计作品赏析_现在有什么技能培训班_制作网站建设入门

如何制作自己的网站 可放广告_网页界面设计作品赏析_现在有什么技能培训班_制作网站建设入门

时间:2025/7/14 13:09:16来源:https://blog.csdn.net/2203_75582171/article/details/142970861 浏览次数:0次
如何制作自己的网站 可放广告_网页界面设计作品赏析_现在有什么技能培训班_制作网站建设入门


解题思路:

        首先,不能使用暴力枚举,时间为O(n2),超时。以下为正确做法:

        假设找到一段区间(其和>=m),如上图黄色部分,那么该区间加上i后面的元素形成的新区间和都>=m,因此以该区间为基础就有n-i+1个区间符合要求。

        那么我们只需要从1开始找到每一个恰好大于等于m的黄色区间,再依次把每一个黄色区间为基础的区间的个数相加就得到答案。


AC代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+9;
int a[N];
ll m;
// 依次找出区间和>=m的滑动窗口,j++ 
int main()
{ll sum = 0,ans = 0;int n, j = 1;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];sum += a[i];if(sum >= m){ans += (n-i+1);while(j <= i && sum >= m){  // 数组从1开始序号递增,所以当序号i>=j时区间合法 sum -= a[j];j++;if(sum >= m)ans += (n-i+1);} }}cout << ans << '\n';    return 0;
}

知识点:

        双指针,滑动窗口

关键字:如何制作自己的网站 可放广告_网页界面设计作品赏析_现在有什么技能培训班_制作网站建设入门

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: