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

 1 /*
 2     贪心 + 模拟：首先，如果蜡烛的燃烧时间小于最少需要点燃的蜡烛数一定是-1(蜡烛是1秒点一支)，
 3             num[g[i]]记录每个鬼访问时已点燃的蜡烛数，若不够，tmp为还需要的蜡烛数，
 4             然后接下来的t秒需要的蜡烛都燃烧着，超过t秒，每减少一秒灭一支蜡烛，好！！！
 5     详细解释：http://blog.csdn.net/kalilili/article/details/43412385
 6 */
 7 #include <cstdio>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <string>
12 using namespace std;
13 
14 const int MAXN = 1e3 + 10;
15 const int MAXG = 300 + 10;
16 const int INF = 0x3f3f3f3f;
17 int g[MAXG];
18 int num[MAXN];
19 
20 int main(void)        //Codeforces Round #288 (Div. 2) C. Anya and Ghosts
21 {
22     #ifndef ONLINE_JUDGE
23         freopen ("C.in", "r", stdin);
24     #endif
25 
26     int m, t, r;
27 
28     scanf ("%d%d%d", &m, &t, &r);
29     for (int i=1; i<=m; ++i)
30         scanf ("%d", &g[i]);
31 
32     if (t < r)
33     {
34         puts ("-1");    return 0;
35     }
36     int ans = 0;
37     for (int i=1; i<=m; ++i)
38     {
39         if (num[g[i]] < r)
40         {
41             int tmp = r - num[g[i]];
42             ans += tmp;
43             for (int j=g[i]+1; j<=g[i]-tmp+t; ++j)    num[j] += tmp;
44             for (int j=g[i]-tmp+t+1; j<=g[i]+t-1; ++j)    num[j] += (--tmp);
45         }
46     }
47 
48     printf ("%d
", ans);
49 
50     return 0;
51 }
编译人生，运行世界！