Codeforces 898D Alarm Clock

链接

传送门

题意

有\(n\)个闹钟和他们响的时间，如果连续\(m\)分钟内, 有至少\(k\)个闹钟响起，Vitalya就会起床，问至少关掉多少个闹钟才能让Vitalya一整天不起床。其中\((1 \leq k \leq n \leq 2 \times 10^5, 1 \leq m \leq 10^6)\)。

思路

每次连续\(m\)分钟响起的闹钟个数达到\(k\)个，关掉最后一个就好了🤔。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

typedef long long LL;

using namespace std;

const int maxn = 200010;

deque<int> q;
int a[maxn];

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a + 1, a + n + 1);
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    while (!q.empty() && q.front() + m <= a[i]) {
      q.pop_front();
    }
    q.push_back(a[i]);
    if (q.size() >= k) {
      q.pop_back();
      ++ans;
    }
  }
  printf("%d\n", ans);
  return 0;
}