codeforces508C

概述 题意：共有m个鬼，每个鬼的到访时间为wi，且就存在wi这1秒。现有r根蜡烛，每根蜡烛的燃烧时间为t，每次鬼出现时保持r根蜡烛为点燃的状态，且蜡烛点燃需要1秒的时间，若x时刻点燃蜡烛，蜡烛的存在时间为x+1到x+r，x+r的下一个时刻蜡烛就熄灭了。求鬼出现的这m次中，需要点燃蜡烛的最小数量。 思路：若t<r时，不能满足在第i个鬼处同时燃烧着r根蜡烛，因为在一个时刻一次只能点燃一根蜡烛，所以直接输出

 题意：共有m个鬼，每个鬼的到访时间为wi，且就存在wi这1秒。现有r根蜡烛，每根蜡烛的燃烧时间为t，每次鬼出现时保持r根蜡烛为点燃的状态，且蜡烛点燃需要1秒的时间，若x时刻点燃蜡烛，蜡烛的存在时间为x+1到x+r，x+r的下一个时刻蜡烛就熄灭了。求鬼出现的这m次中，需要点燃蜡烛的最小数量。

思路：若t<r时，不能满足在第i个鬼处同时燃烧着r根蜡烛，因为在一个时刻一次只能点燃一根蜡烛，所以直接输出-1

t>=r时，首先记录w1（第一个鬼出现的时刻）前点燃r根蜡烛的时刻，并记录总和（第一次放所有蜡烛的个数r）。之后依次比较（记录蜡烛的这几个时刻+蜡烛的燃烧时间t）与下一个wi之间的大小若前者小于后者表明最后蜡烛燃着时间到不了wi，那么总和就要加一（需要再点燃一根新的蜡烛）。每次循环只要考虑当前wi下时之前记录的蜡烛的时刻，并且更新时刻，更新时刻时，用当前wi的值减去num++（num初值为1）

完整代码

#include <bits/stdc++.h>using namespace std;int w[305],c[305];int main(){    int m,t,r,ans=0;    cin>>m>>t>>r;    for(int i=1;i<=m;i++)        cin>>w[i];    if(t<r)        cout<<-1<<endl;    else    {        for(int i=1;i<=r;i++)        {            c[i]=(w[1]-r)+(i-1);            ans++;        }        for(int i=2;i<=m;i++)        {            int num=1;            for(int j=1;j<=r;j++)            {                if(c[j]+t<w[i])                {                    ans++;                    c[j]=w[i]-num++;                    }                }            }        cout<<ans<<endl;        }    return 0;}

总结

以上是内存溢出为你收集整理的codeforces508C全部内容，希望文章能够帮你解决codeforces508C所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。