当前位置: 首页 > news >正文

题解:CF332B Maximum Absurdity

CF332B
CF332B

暴力思路

题目要我们找两个不重叠的区间,并使区间的值最大。那我们可以考虑使用双重循环搭配前缀和暴力求最大值。代码如下。

for(int i=1;i<=n;i++)
{ll l=sum[i+k-1]-sum[i-1],maxx;for(int j=i+k;j<=n;j++){maxx=l+sum[j+k-1]-sum[j-1];if(maxx>ans.sum){ans.x=i;ans.y=j;ans.sum=maxx;}}
}

但是暴力的时间复杂度是一定会超时的。那我们考虑一下优化。

优化思路

我们可以思考一下如何把第二层循环给优化掉。我们可以用一个结构体数组 m a x x [ i ] maxx[i] maxx[i] 来记录 i ∼ n i \sim n in 的最大的区间值,并记录这个区间的起点。这样我们就把第二层循环给优化掉了。

最重要的注意数据范围,要开 long long

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll unsigned long long
#define lhs printf("\n");
using namespace std;
const int N=3e5+10;
const int M=2024;
const int inf=0x3f3f3f3f;
ll n,k;
ll a[N]; 
ll sum[N];
struct node
{ll num;int id;
}maxx[N];
struct nodee
{ll sum;ll x,y;
}ans;
int main()
{scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];//前缀和} for(int i=n;i>=1;i--){if(i+k-1>n)continue;ll l=sum[i+k-1]-sum[i-1];//更新最大值if(maxx[i+1].num>l){maxx[i].num=maxx[i+1].num;maxx[i].id=maxx[i+1].id;}else{maxx[i].num=l;maxx[i].id=i;}} for(int i=1;i<=n;i++){if(i+k-1>n)continue;ll l=sum[i+k-1]-sum[i-1];ll r=maxx[i+k].num,rid=maxx[i+k].id;if(l+r>ans.sum){ans.x=i;ans.y=rid;ans.sum=r+l;}} printf("%lld %lld",ans.x,ans.y);return 0;
}
http://www.lryc.cn/news/495399.html

相关文章:

  • Vue 集成和使用 SQLite 的完整指东
  • 【JVM什么时候触发YoungGC和FullGC】
  • ubuntu配置网络
  • 第十一课 Unity编辑器创建的资源优化_预制体和材质篇(Prefabs和Materials)详解
  • 2024.11.29(单链表)
  • 基于深度学习和卷积神经网络的乳腺癌影像自动化诊断系统(PyQt5界面+数据集+训练代码)
  • opengl 三角形
  • 23种设计模式-抽象工厂(Abstract Factory)设计模式
  • 手机上怎么拍证件照,操作简单且尺寸颜色标准的方法
  • IDEA报错: java: JPS incremental annotation processing is disabled 解决
  • OCR实现微信截图改名
  • 第一届“吾杯”网络安全技能大赛 Writeup
  • 再谈Java中的String类型是否相同的判断方法
  • <一>51单片机环境
  • 【0x0001】HCI_Set_Event_Mask详解
  • 第三方Express 路由和路由中间件
  • 七、Python —— 元组、集合和字典
  • Aes加解密
  • 【时时三省】Tessy 故障入侵 使用教程
  • .NET 9 AOT的突破 - 支持老旧Win7与XP环境
  • CondaValueError: Malformed version string ‘~‘: invalid character(s).
  • 01-Ubuntu24.04LTS上安装PGSQL
  • Esp32使用micropython基于espnow实现语音对讲机
  • Docker 容器隔离关键技术:SELinux
  • Java并发07之ThreadLocal
  • 【单细胞数据库】癌症单细胞数据库CancerSEA
  • Rsa加解密 + 签名验签
  • bugku-web-留言板1
  • 进程状态的学习
  • Vue 2.0->3.0学习笔记(Vue 3 (四)- Composition API 的优势)