贪心+模拟 Codeforces Round #288 (Div. 2) C. Anya and Ghosts

题目传送门

 /*

     贪心 + 模拟：首先，如果蜡烛的燃烧时间小于最少需要点燃的蜡烛数一定是-1(蜡烛是1秒点一支)，

             num[g[i]]记录每个鬼访问时已点燃的蜡烛数，若不够，tmp为还需要的蜡烛数，

             然后接下来的t秒需要的蜡烛都燃烧着，超过t秒，每减少一秒灭一支蜡烛，好！！！

     详细解释：http://blog.csdn.net/kalilili/article/details/43412385

 */

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <string>

 using namespace std;

 const int MAXN = 1e3 + ;

 const int MAXG =  + ;

 const int INF = 0x3f3f3f3f;

 int g[MAXG];

 int num[MAXN];

 int main(void)        //Codeforces Round #288 (Div. 2) C. Anya and Ghosts

 {

     #ifndef ONLINE_JUDGE

         freopen ("C.in", "r", stdin);

     #endif

     int m, t, r;

     scanf ("%d%d%d", &m, &t, &r);

     for (int i=; i<=m; ++i)

         scanf ("%d", &g[i]);

     if (t < r)

     {

         puts ("-1");    return ;

     }

     int ans = ;

     for (int i=; i<=m; ++i)

     {

         if (num[g[i]] < r)

         {

             int tmp = r - num[g[i]];

             ans += tmp;

             for (int j=g[i]+; j<=g[i]-tmp+t; ++j)    num[j] += tmp;

             for (int j=g[i]-tmp+t+; j<=g[i]+t-; ++j)    num[j] += (--tmp);

         }

     }

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

     return ;

 }

贪心+模拟 Codeforces Round #288 (Div. 2) C. Anya and Ghosts的相关教程结束。