2013年8月31日

UVa 10901 - Ferry Loading III

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct Car {
  bool operator<(const Car & other) const {
    return id < other.id;
  }
  int id, time;
};

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, t, m;
    scanf("%d%d%d", &n, &t, &m);
    queue<Car> left, right;
    for (int i = 0; i < m; i++) {
      int time;
      char side[9];
      scanf("%d%s", &time, side);
      if (side[0] == 'l') {
        left.push((Car){i, time});
      } else {
        right.push((Car){i, time});
      }
    }
    left.push((Car){m + 1, 2e9});
    right.push((Car){m + 2, 2e9});
    int time = 0;
    bool l = true;
    vector<Car> ans;
    while (left.size() + right.size() > 2) {
      int carry = 0;
      while (l) {
        if (left.front().time > time) {
          if (right.front().time < left.front().time) {
            time = max(time, right.front().time);
            break;
          }
          time = left.front().time;
        }
        while (left.front().time <= time && carry < n) {
          ans.PB((Car){left.front().id, time + t});
          left.pop();
          carry++;
        }
        break;
      }
      while (!l) {
        if (right.front().time > time) {
          if (left.front().time < right.front().time) {
            time = max(time, left.front().time);
            break;
          }
          time = right.front().time;
        }
        while (right.front().time <= time && carry < n) {
          ans.PB((Car){right.front().id, time + t});
          right.pop();
          carry++;
        }
        break;
      }
      time += t;
      l = !l;
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
      printf("%d\n", ans[i].time);
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言