#12568. 节能采样与公约数警报
节能采样与公约数警报
题目:节能采样与公约数警报
🗂️ 任务信息 时间限制:1s 内存限制:512 MB 难度:⭐⭐⭐(滑动窗口 + gcd)
📝 题目描述
在一座实验基地中,传感器每秒产生一次“能耗值”。工程师要进行一次连续采样,采样必须包含 恰好 (K) 秒的数据。
给定长度为 (n) 的正整数数组 a,第 (i) 秒能耗为 (a_i)。
你需要完成两件事:
-
在所有长度恰好为 (K) 的连续子数组中,找到最小的子数组和,记为
-
设取得最小和的那段子数组为 (W)(若最小和出现多次,取最靠左的一段),计算
判断 是否存在大于 1 的公约数,即判断:
📥 输入格式
第一行输入两个整数:n K
第二行输入 n 个正整数:a1 a2 ... an
📤 输出格式
输出两行:
- 第一行输出最小子数组和
- 第二行输出
YES或NO:YES表示NO表示
📚 样例
输入:
8 3
6 10 15 3 5 7 2 9
输出:
14
NO
说明:长度为 3 的窗口和最小的是 [5,7,2],和为 14。
该窗口元素 gcd 为 (\gcd(5,7,2)=1),所以 (\gcd(14,1)=1),输出 NO。
📏 数据范围(建议)
- 子数组和使用 64 位整数(
long long)
💡 训练点
- 定长滑动窗口求最小和((O(n)))
gcd运算((O(K)),只对最优窗口算一次)
统计
相关
在下列比赛中: