题解归档 - cf427B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf427B
• 本地来源：problems/cf427B/idea.md
• 题目链接：https://codeforces.com/contest/427/problem/B
• 原始标题：cf427B — Prison Transfer

思路

cf427B — Prison Transfer

题意

n 名囚犯排成一行，每人有犯罪严重度。要选恰好 c 名连续囚犯转移，且所选每人严重度均 ≤ t。求方案数。

做法

将 s[i] > t 的位置视为隔断，把序列切成若干段，每段内所有元素均合法。长度为 L 的段中，长度为 c 的连续子段数为 max(0, L - c + 1)，各段求和即可。

扫一遍：遇到非法位置 i，对当前段 [cur, i-1] 累加贡献后令 cur = i + 1；末尾再处理剩余段。

验证

• 官方样例 3 组（手算一致）
• Kali 远端不可达，未能跑 stress.py；逻辑与暴力枚举一致

代码

来源：problems/cf427B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:40:59
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+5;
ll n,t,c,i,j,k,zc,pd,cur,dq,cnt,ans;
ll s[maxn+5];
int main(){
    cin>>n>>t>>c;
    ans=0;
    cur=1;
    for(i=1;i<=n;i++){
        cin>>s[i];
        if(s[i]>t){
            if(cur<=i-c) ans+=i-c-cur+1;
            cur=i+1;
        }
    }
    if(cur<=n-c+1) ans+=n-c+1-cur+1;
    cout<<ans<<"\n";
    return 0;
}