Codeforces 898D - Alarm Clock

传送门：http://codeforces.com/contest/898/problem/D

有n个闹钟，第i(1≤i≤n)个闹钟将在第a_i(1≤a_i≤10⁶)分钟鸣响，鸣响时间为一分钟。当在连续的m分钟内，有至少k个闹钟鸣响，则会被叫醒。现要求关闭一些闹钟，使得在任意连续的m分钟内，鸣响的闹钟数量恒小于k。

可以贪心地求解这个问题。

首先，设置一个bool数组ison[]，当有闹钟在第i分钟鸣响时，记ison[i]=1，否则ison[i]=0。

接下来，扫描整个时间区间[0..MAX_A]。记当前时间为i，记在区间(i-m..i]={i-m+1,...,i-1,i}上开启的闹钟个数为cnt。扫描时维护cnt，当cnt≥k时，将当前的闹钟关闭即可。

参考程序如下：

#include <stdio.h>

#include <stdbool.h>

#define MAX_A 1000001

bool ison[MAX_A];

int main(void)

{

    int n, m, k;

    scanf("%d%d%d", &n, &m, &k);

    for (int i = ; i < n; i++) {

        int a;

        scanf("%d", &a);

        ison[a] = true;

    }

    int ans = , cnt = ;

    for (int i = ; i < MAX_A; i++) {

        if (ison[i]) cnt++;

        if (i - m >  && ison[i - m]) cnt--;

        if (cnt >= k) {

            ison[i] = false;

            cnt--;

            ans++;

        }

    }

    printf("%d\n", ans);

    return ;

}

巴特西

Codeforces 898D - Alarm Clock

最新文章

热门文章