2904 窗口及格人数
大约 1 分钟
2904 窗口及格人数
【算法】 滑动窗口
【C++】 滑动窗口、计数
【难度】 入门
一、题目简述
记录了 天的考试成绩,求所有连续 天中,及格人数(成绩 )的最大值。
数据范围:,成绩 。
二、解题思路
定长滑动窗口统计及格人数。窗口右移时,维护窗口内的及格人数 cnt:
- 新进入:若
score[i] >= 60,cnt++ - 离开:若
score[i-k] >= 60,cnt-- - 每步用
max更新答案
不需要额外数据结构,只需一个整数变量记录及格人数即可。
手动模拟 [55, 62, 78, 45, 90, 58, 72],k=3:
| 步骤 | 窗口范围 | 窗口成绩 | 及格人数(cnt) | 操作 | ans |
|---|---|---|---|---|---|
| 初始(前3个) | [1, 3] | 55, 62, 78 | 2 | 55<60 不计, 62≥60, 78≥60 | 2 |
| 右移 | [2, 4] | 62, 78, 45 | 2 | +1(a₄=45<60不+), -1(a₁=55<60不-) | 2 |
| 右移 | [3, 5] | 78, 45, 90 | 2 | +1(90≥60), -1(62≥60)→不变 | 2 |
| 右移 | [4, 6] | 45, 90, 58 | 1 | +0(58<60), -1(78≥60) | 2 |
| 右移 | [5, 7] | 90, 58, 72 | 2 | +1(72≥60), -1(45<60) | 2 |
最大及格人数 = 2。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int score[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> score[i];
// 第一个窗口的及格人数
int cnt = 0;
for (int i = 1; i <= k; i++)
if (score[i] >= 60) cnt++;
int ans = cnt;
// 滑动窗口
for (int i = k + 1; i <= n; i++) {
if (score[i] >= 60) cnt++; // 新进入
if (score[i - k] >= 60) cnt--; // 离开
ans = max(ans, cnt);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,每个成绩被检查恰好两次(进入一次、离开一次)。
- 空间复杂度:,用于存储成绩数组
score。
