「Transmitting Levels」Solution

ops/2025/3/16 8:11:13/

简述题意

给定一个 n n n 个元素的环形数组 a a a q q q 次查询,每次给定一个 k k k,将数组划分为若干个连续段,使得每一段的和都不超过 k k k,最小化连续段个数。

  • 2 ≤ n ≤ 1 0 6 , 1 ≤ q ≤ 50 2 \le n \le 10^6, 1 \le q \le 50 2n106,1q50
  • 1 ≤ a i ≤ 1 0 9 , max ⁡ { a i } ≤ k ≤ 1 0 15 1 \le a_i \le 10^9,\max\{a_i\} \le k \le 10^{15} 1ai109,max{ai}k1015

思路

先破环成链,然后求前缀和 p r e pre pre
对于每一个 i i i,不妨先双指针求出 n x t i nxt_i nxti,表示最大的满足 p r e n x t i − p r e i − 1 ≤ k pre_{nxt_i} - pre_{i-1} \le k prenxtiprei1k 的点。
显然,如果我们已经知道了某个连续段的起点,那么贪心的往后跳到 n x t i + 1 nxt_i+1 nxti+1,答案是固定的。
然而,如果直接枚举 n n n 个起点,时间复杂度接受不了,考虑优化。
我们可以发现,无论怎么划分,连续段长度都存在一个下限,那就是 min ⁡ { n x t i − i + 1 } \min\{nxt_i-i+1\} min{nxtii+1},那么每次贪心的时间复杂度即为 O ( n min ⁡ { n x t i − i + 1 } ) O(\dfrac{n}{\min\{nxt_i-i+1\}}) O(min{nxtii+1}n)。不妨令 n x t i − i + 1 nxt_i-i+1 nxtii+1 最小的这个点为 x x x

考虑进一步优化:减少枚举起点的数量。

观察上面那个式子的分母,可以想到,无论怎么划分,一定有一个连续段的起点在 [ x , n x t x + 1 ] [x,nxt_x+1] [x,nxtx+1],否则一定划分出来有一个连续段的和大于 k k k,这是显然的。所以枚举起点的复杂度为 O ( n x t x − x + 1 ) O(nxt_x-x+1) O(nxtxx+1)

单次查询的时间复杂度为 O ( n ) O(n) O(n)

代码

很简单的一道 2400 2400 2400

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 5;
int n , q , a[MAXN] , nxt[MAXN];
ll pre[MAXN] , k;
int Path(int now) {if (now > n) now -= n;int l = 0 , sum = 0;while(l < n) {l += nxt[now] - now + 1;sum ++;now = nxt[now] + 1;}return sum;
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr) , cout.tie(nullptr); cin >> n >> q;for (int i = 1 ; i <= n ; i ++) cin >> a[i] , a[i + n] = a[i];for (int i = 1 ; i <= 2 * n ; i ++) pre[i] = pre[i - 1] + a[i];while(q --) {cin >> k;int len = 1e9 , st;for (int i = 1 , j = 1 ; i <= 2 * n ; i ++) {while(j < 2 * n && pre[j + 1] - pre[i - 1] <= k) j ++;nxt[i] = j;if (nxt[i] - i + 1 < len && i <= n) st = i , len = nxt[i] - i + 1;}int ans = 1e9;for (int i = st ; i <= nxt[st] + 1 ; i ++) ans = min(ans , Path(i));cout << ans << '\n';}return 0;
}

http://www.ppmy.cn/ops/27418.html

相关文章

Docker容器配置进阶

一、容器的自动重启 Docker提供重启策略选项控制容器退出时或Docker重启时是否自动启动该容器。重启策略能够确保关联的多个容器按照正确的顺序启动。Docker建议使用重启策略&#xff0c;并避免使用进程管理器启动容器。运行容器时可以使用--restart选项指定重启策略。容器的重…

Spring Boot集成Spring AI实现快速接入openAI

1.什么是Spring AI&#xff1f; Spring AI API 涵盖了广泛的功能。每个主要功能都在其专门的部分中进行了详细介绍。为了提供概述&#xff0c;可以使用以下关键功能&#xff1a; 跨 AI 提供商的可移植 API&#xff0c;用于聊天、文本到图像和嵌入模型。支持同步和流 API 选项。…

linux系统的rsync命令实现本机到远程主机之间目录的复制和同步

一、rsync命令介绍 在Linux中&#xff0c;rsync 是一个强大的命令行工具&#xff0c;用于同步文件和目录。它可以在本地或通过网络在远程系统之间复制文件。 二、远程目录复制的条件 1、系统要已经安装rsync工具 要使用 rsync 复制远程目录&#xff0c;需要确保系统上安装了 …

CSS常用属性之(列表、表格、鼠标)属性,(如果想知道CSS的列表、表格、鼠标相关的属性知识点,那么只看这一篇就足够了!)

前言&#xff1a;在学习CSS的时候&#xff0c;必不可少的就要学习选择器和常见的属性&#xff0c;而本篇文章讲解的是CSS中的列表、表格、背景、鼠标属性。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客 大致了解一下本篇文章…

搭建和配置Stable Diffusion环境,超详细的本地部署教程

跃然纸上的创意、瞬息万变的想象&#xff0c;Stable Diffusion以AI的力量赋予您无限创作可能。在这篇详尽的本地部署教程中&#xff0c;我们将携手走进Stable Diffusion的世界&#xff0c;从零开始&#xff0c;一步步搭建和配置这个强大的深度学习环境。无论您是热衷于探索AI艺…

maven聚合,继承等方式

需要install安装到本地仓库&#xff0c;或者私服&#xff0c;方可使用自己封装项目 编译&#xff0c;测试&#xff0c;打包&#xff0c;安装&#xff0c;发布 parent: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://mav…

TiDB 分布式数据库常用操作详解

TiDB 是一个开源的分布式关系数据库&#xff0c;它支持水平扩展、高可用性、在线DDL以及兼容MySQL协议。V哥在使用过 TiDB后&#xff0c;感觉就是两个字“倍爽”&#xff0c;因为 TiDB是天然的分布式数据库&#xff0c;让你彻底告别分库分表的时代&#xff0c;具说某呼就是使用…

深入理解Java消息中间件-消息中间件的高可用和故障转移

消息中间件在现代企业应用中扮演着至关重要的角色&#xff0c;它负责异步消息传递&#xff0c;解耦系统组件&#xff0c;以及确保系统的高性能。然而&#xff0c;为了保证系统的稳定性和可靠性&#xff0c;消息中间件需要具备高可用性和故障转移的能力。本文将以Apache Kafka为…