题解：CF508C Anya and Ghosts

Rex01 · 2025-02-15 09:45:06 · 题解

CF508C 题目传送门

题目大意

夜市中管理方会在午夜后进行 m 次检查，第 i 次检查在午夜后的第 w_i 秒进行，每次检查持续 1 秒钟，要求每次检查夜市里至少有 r 根蜡烛在燃烧。已知每根蜡烛能燃烧 t 秒，点燃一根蜡烛需要 1 秒。你的任务是要使每次检查都合格，最少需要多少根蜡烛。

解决思路

首先考虑特殊情况，即输出 -1。如果每根蜡烛燃烧的时间小于最小的蜡烛根数（t < r），即不满足要求，则直接输出 -1。每次鬼魂到达时，检查之前点燃的蜡烛是否还能覆盖当前时间。如果不能，就点燃新蜡烛。最后输出总共点燃的蜡烛数量。

代码展示

#include <iostream>
using namespace std;

int m, t, r, w, a[1010];
//a[]表示燃烧的蜡烛的结束时间 
int x, y, ans;
//x表示燃烧的蜡烛的起始下标 
//y表示下一个要被点燃的蜡烛下标

int main() 
{
    cin >> m >> t >> r;
    if(t < r) 
    {//如果每根蜡烛燃烧的时间小于最小的蜡烛根数，
        puts("-1");//即不满足情况，则直接输出-1
        return 0;
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> w;
        while(x < y && a[x] < w) x++;
        for(int j = w - r + y - x; j < w;j++)
        {
            a[y++] = j + t;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}