你所在城市的监狱有n名囚犯。由于监狱无法容纳所有囚犯市长决定将c名囚犯转移到另一个城市的监狱。为此他让n名囚犯排成一队胸前写有一个数字。这个数字是他/她所犯罪行的严重程度。数字越大罪行越严重。然后市长告诉你选择c名囚犯转移到另一个监狱。他还提出了两个条件。它们是选择的c名囚犯必须形成一个连续的囚犯段。任何被选择的囚犯的罪行等级不得大于t。因为这将使囚犯成为严重罪犯市长不想冒着转移过程中他逃跑的风险。找出你可以选择的c名囚犯的方式数量。输入输入的第一行将包含三个用空格分隔的整数n(1 ≤n≤ 2·105)、t(0 ≤t≤ 109) 和c(1 ≤c≤n)。下一行将包含n个用空格分隔的整数第ith个整数是囚犯罪行的严重程度ith。罪行严重程度的值将是非负的并且不会超过 109。输出打印一个整数 — 你可以选择的c名囚犯的方式数量。示例InputcopyOutputcopy4 3 3 2 3 1 12InputcopyOutputcopy1 1 1 20InputcopyOutputcopy11 4 2 2 2 0 7 3 2 2 4 9 1 46一、 题目剖析与核心转化【题目大意】监狱里有 n 名囚犯排成一排每人都有一个罪行值。市长要求选出连续的 c 名囚犯进行转移且这 c 个人中任何一个人的罪行值都不能超过 t。求有多少种合法的选择方案。【数据范围】1≤c≤n≤2*10^5罪行值 t≤10^9。【等价转化】读完题我们会立刻想出两种解题视角微观视角找连续合法段只要遇到罪行值 ≤t 的囚犯队伍就继续往右拉长一旦遇到 t 的囚犯这条“链”就彻底断了必须越过他重新开始。宏观视角滑动窗口最值在一个长度固定为 c 的滑动窗口中只要这个窗口里的最大罪行值≤t那这个窗口就是合法的。这两种视角分别对应了我们接下来的“双指针法”和“单调队列法”。二、 解法一双指针思考过程既然要求连续的 c 个人都合法我们可以用两个指针l左边界和r右边界来模拟一根“卷尺”。 尺子的右端点r不断向右探索。只要遇到合法的囚犯尺子就拉长只要拉长的长度达到了 c方案数就加一。核心亮点一旦a[r]遇到一个 t 的超级罪犯说明以他为中心的所有跨越他的区间全部作废。此时左边界l不需要一步步慢吞吞地挪动而是直*“瞬移”到 r1 的位置重新开始拉尺子。时空复杂度时间复杂度O(N)。右指针r永远只往前走不回头。空间复杂度O(N)。仅需存储原数组。完整代码双指针//区间取数1 //codefoorce 427B //第一种做法 双指针 #include iostream using namespace std; int n,t,c; int a[2000010];//原数列 int cnt;//选法总数 int main() { //n名囚犯 罪行最大为t 连续的c名囚犯 cinntc; for(int i1;in;i) cina[i]; int l1;//被选择的连续囚犯合法段的左端点 int r1;//被选择的连续囚犯合法段的右端点 //左右端点不能超过边界 while(lnrn){ //当区间内所有囚犯罪行都小于等于t时 //只要右端点合法就不断延伸 while(rna[r]t){ //当积累的连续长度达到c时产生一种合法方案 if(r-l1c){ //代表选择多一种 cnt; } //右端点继续往右探索 r; } if(rna[r]t){//当右端点对应囚犯罪行大于t时 lr1;//直接让左端点跨过右端点变成当前右端点的下一个囚犯 rl;//右端点变成左端点 } } coutcnt; return 0; }三、 解法二单调队列滑动窗口极值验证思考过程如果我们直接套用“求定长区间最大值”的通用模型这道题就是一道标准的单调队列模板题。 我们维护一个长度为 c 的滑动窗口利用单调递减队列时刻掌控窗口内的最大值。只要当前窗口成型长度 ≥c且队首即最大值 ≤t则方案数加一。核心亮点盘后清算机制很多同学在写单调队列时容易把“原数组的下标”和“队列数组的下标”搞混。 在我的代码中队列q里只存储原数组的下标。同时在每天结账后利用if(i - q[front] 1 c) front;精准判断队首的最大值是否刚好踩在窗口的淘汰边缘如果是则提前让他“退休出队”。这是一种不容易越界的生命周期管理方式。时空复杂度时间复杂度O(N)。每个元素最多入队一次、出队一次均摊 O(1)。空间复杂度O(N)。需要原数组和单调队列数组。完整代码单调队列法//第二种做法 单调队列 //找出每个区间最大值看有多少区间最大值小于等于t就是有多少区间方案满足要求 #include iostream using namespace std; int n,t,c; int a[200010];//原数列 //单调队列 队首应为最大罪行 所以为一个单调递减队列 int q[200010]; int front1,rear0;//队首指针 队尾指针 int cnt;//记录方式数 int main(){ //n名囚犯 罪行最大为t 连续的c名囚犯 cinntc; for(int i1;in;i) cina[i]; for(int i1;in;i){ //当队列非空且当前囚犯罪行大于队尾囚犯罪行时 //弹出队尾 while(frontreara[i]a[q[rear]]) rear--; //把当前囚犯存进队尾 q[rear]i; //如果当前区间长度为c if(icfrontrear){ //如果区间内最大罪行小于等于t //则方案数加一 if(a[q[front]]t) cnt; //这一轮的front已经被用了如果它刚好在最左端 //下一轮就过期了就不能用了就出队 //比喻 //盘后清算如果当前的队首老大刚好站在窗口的最左端 //意味着明天他就会滑出窗口所以今天结完账就立刻让他退休 if(i-q[front]1c) front; } } coutcnt; return 0; }四、 易错点总结对于这道题双指针法因为贴近物理本质代码更加直白但单调队列法提供了极强的泛化能力如果题目改成“求每个区间的最大值之和”双指针将彻底失效而单调队列只需改动一行代码。警惕“双重下标”混淆在写单调队列时务必死死盯住front和rear是队列的指针而q[front]才是元素在原数组中真实的物理坐标。算生命周期时必须用q[front]参与计算。