一、问题重述
我们需要从n名按入狱时间排序的罪犯中,找出所有长度为c的连续子序列,使得这些子序列的罪行值之和不超过t。这是一个典型的滑动窗口问题,适合用高效算法解决。
#include <iostream>
#include <vector>
using namespACe std;
int main() {
int n, t, c;
while (cin >> n >> t >> c) { // 处理多组测试数据
vector<int> crimes(n);
for (int i = 0; i < n; ++i) {
cin >> crimes[i]; // 读取每个罪犯的罪行值
}
int count = 0; // 记录符合条件的窗口数量
long long window_sum = 0; // 当前窗口的和,使用long long防止溢出
// 初始化第一个窗口
for (int i = 0; i < c; ++i) {
window_sum += crimes[i];
}
if (window_sum <= t) {
count++;
}
// 滑动窗口:每次移动一位
for (int i = c; i < n; ++i) {
// 减去离开窗口的元素,加上新进入窗口的元素
window_sum = window_sum - crimes[i - c] + crimes[i];
if (window_sum <= t) {
count++;
}
}
cout << count << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")