CF508C

liuzhongrui · 2024-04-25 20:11:47 · 题解

思路

我们先来判断输出 -1 的情况，题目中说到每根蜡烛可以燃烧 t 秒，鬼魂来时最少要有 r 跟蜡烛被点燃，而每根蜡烛被点燃需要 1 秒钟的时间，很容易发现，当 t<r 时，即每根蜡烛燃烧时间小于最少要被点燃的蜡烛数时，不可能存在最少要有 r 跟蜡烛被点燃这个条件，证明也很简单，由于每根蜡烛被点燃需要 1 秒钟的时间，因此点燃 r 根蜡烛至少需要 r 秒，当 t<r 时总会存在有蜡烛撑不到 r 秒。这种情况输出 -1 即可。

接下来的情况都是合法的了。我们逐个读入每个鬼魂的到达时间 w_i。在每次读入一个到达时间后，检查之前点燃的蜡烛是否可以覆盖当前鬼魂的到达时间。如果无法覆盖，则点燃足够的新蜡烛以覆盖到达时间。在这个过程中，记录了点燃的蜡烛总数，最后输出点燃蜡烛的总数即可。

Code

十分简短。

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int m,t,r;
int main() {
    scanf("%d%d%d",&m,&t,&r);
    if(t<r) {
        puts("-1");
        return 0;
    }
    int st=0,ed=0,ans=0;;
    while(m--) {
        int w;
        scanf("%d",&w);
        while(st<ed&&a[st]<w) st++;
        for(int i=w-r+ed-st; i<w; i++){
            a[ed++]=i+t;
            ans++;
        } 
    }
    printf("%d\n",ans);
    return 0;
}