AOJ 2298 - Starting Line

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2298

解法

ニンジンを使っていないときは，ニンジンをとった地点で使うのが最適．

ニンジンを使っているときは，まだニンジンを持てる場合は，使わずに持っておいて，ニンジンの効果が切れたときに使うのが最適．

これ以上持てない場合は，その場で使ってしまうのが最適．

このような戦略をイベントドリブンなかんじで実装した．

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct event {
 7   int pos;
 8   enum event_type { CARROT, DOWN, GOAL };
 9   event_type ev;
10   event(int p, event_type e) : pos(p), ev(e) {}
11   bool operator<(const event& that) const { return pos > that.pos; }
12 };
13 
14 int main()
15 {
16   int N, K, T, U, V, L;
17   cin >> N >> K >> T >> U >> V >> L;
18   priority_queue<event> q;
19   q.push(event(L, event::GOAL));
20   for (int i = 0; i < N; i++) {
21     int d;
22     cin >> d;
23     q.push(event(d, event::CARROT));
24   }
25 
26   bool running = false;
27   int running_dist = 0;
28   int prev = 0;
29   int have = 0;
30   int ignore = 0;
31   bool goal = false;
32   while (!q.empty() && !goal) {
33     const event::event_type ev = q.top().ev;
34     const int pos = q.top().pos;
35     q.pop();
36     if (running) {
37       running_dist += pos - prev;
38     }
39     switch (ev) {
40       case event::CARROT:
41         if (running) {
42           if (have == K) {
43             ++ignore;
44             q.push(event(pos+V*T, event::DOWN));
45           } else {
46             ++have;
47           }
48         } else {
49           q.push(event(pos+V*T, event::DOWN));
50           running = true;
51         }
52         break;
53       case event::DOWN:
54         if (ignore > 0) {
55           --ignore;
56         } else if (have > 0) {
57           --have;
58           q.push(event(pos+V*T, event::DOWN));
59         } else {
60           running = false;
61         }
62         break;
63       case event::GOAL:
64         goal = true;
65         break;
66     }
67     prev = pos;
68   }
69 
70   printf("%.6f\n", running_dist/double(V) + (L-running_dist)/double(U));
71   return 0;
72 }