2013年8月31日

UVa 11034 - Ferry Loading IV

#include <cstdio>
#include <queue>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int size, m;
    scanf("%d%d", &size, &m);
    size *= 100;
    queue<int> left, right;
    for (int i = 0; i < m; i++) {
      int len;
      char side[9];
      scanf("%d%s", &len, side);
      if (side[0] == 'l') {
        left.push(len);
      } else {
        right.push(len);
      }
    }
    left.push(1e9);
    right.push(1e9);
    int trip = 0;
    bool l = true;
    while (left.size() + right.size() > 2) {
      int now = 0;
      if (l) {
        while (now + left.front() <= size) {
          now += left.front();
          left.pop();
        }
      } else {
        while (now + right.front() <= size) {
          now += right.front();
          right.pop();
        }
      }
      trip++;
      l = !l;
    }
    printf("%d\n", trip);
  }
  return 0;
}

沒有留言:

張貼留言