icpc:problems:luogup3662
problems | |
---|---|
名称 | Why Did the Cow Cross the Road II S |
题目编号 | P3662 |
题目链接 | luogu.com.cn/… |
来源 | USACO |
算法分类 | 前缀和 |
难易程度 | 容易 |
Why Did the Cow Cross the Road II S
想法
用前缀和作为差分进行记录个数,直接截取k个来统计和。取最小的区间和。
代码实现
#include<cstdio> const int N = 1e5+10; int sum[N]; int main() { int n, k, b, temp; scanf("%d %d %d", &n, &k, &b); for(int i=1; i<=b; i++) { scanf("%d", &temp); sum[temp] += 1; } for(int i=1; i<=n; i++) sum[i] += sum[i-1]; int mi = N; for(int i=k; i<=n; i++) { if(mi > sum[i] - sum[i-k]) mi = sum[i] - sum[i-k]; } printf("%d", mi); return 0; }
/app/www/public/data/pages/icpc/problems/luogup3662.txt · 最后更改: 2024/03/26 10:33 由 温婕莺