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

守序者的尊严

news 2025/9/20 20:06:26

解题思路

问题分析

这是一个关于监控开关状态和移动策略的问题。监控按照1秒开启、1秒关闭的模式循环工作，小Z只能在监控关闭时通过多个监控。需要计算小Z安全通过所有监控的最短时间。

关键观察

监控状态变化：监控状态每秒交替变化（0→1→0→1...）
移动规则：小Z可以在监控关闭时一次性通过多个连续关闭的监控
策略分析：最优策略是在监控关闭的时段内尽可能多地通过监控

核心思路

原代码采用了一种巧妙的差分方法：

计算相邻监控状态的差值（a[i] - a[i-1]）
每当状态发生变化时（差值不为0），说明需要等待新的时间窗口才能通过
最终时间 = 初始时间1 + 状态变化次数

这是因为：

初始状态第一个监控关闭，可以立即开始移动（计1时间单位）
每次监控状态变化（0→1或1→0）意味着需要等待下一个时间窗口
状态不变的区域可以在同一个时间窗口内一次性通过

代码注释

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
using namespace std;
const int N = 1e6 + 5;
int n,a[N], d[N]; // n:监控数量, a[]:监控状态数组, d[]:状态差分数组
int ans = 1; // 初始化答案为1，因为至少需要1个单位时间（即使所有监控都关闭）int main(){cin>>n; // 输入监控数量for(int i=1;i<=n;i++){cin>>a[i]; // 输入每个监控的初始状态（0或1）// 计算当前监控与前一个监控的状态差值d[i] = a[i] - a[i-1];// 如果状态发生变化（差值不为0），说明需要额外的时间窗口// 因为状态变化意味着监控开关状态交替，需要等待合适的时机才能通过if(d[i] != 0) ans++;}// 输出最终所需时间cout<<ans;return 0;
}