题目链接
题解
记录每一个长为$k$的一段中有几个坏灯,找出答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
#define INF 2000000000 using namespace std; typedef long long ll; bool vis[100005] = {0}; int n, k, b; void (){ scanf("%d%d%d", &n, &k, &b); for(int i = 0; i < b; ++i){ int t; scanf("%d", &t); vis[t] = true; } } void solve(){ int cnt = 0, ans = n; for(int i = 1; i <= k; ++i) if(vis[i]) cnt++; for(int i = k; i <= n; ++i){ ans = min(ans, cnt); if(!ans) break; if(vis[i - k + 1]) cnt--; if(vis[i + 1]) cnt++; } printf("%dn", ans); } int main(){ init(); solve(); return 0; }
|
近期评论