首页 > 代码库 > 【HDOJ】1406 Ferry Loading III

【HDOJ】1406 Ferry Loading III

模拟,注意需要比较队头与当前时间的大小关系。

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 10005 6 #define INF 0xffffff 7  8 typedef struct { 9     int i, t;10 } node_t;11 12 13 node_t Q[2][MAXN];14 int buf[MAXN];15 int rear[2], front[2];16 17 int main() {18     int case_n;19     int n, t, m;20     int i, j, k, a;21     int d;22     char s[7];23 24 #ifndef ONLINE_JUDGE25     freopen("data.in", "r", stdin);26     freopen("data.out", "w", stdout);27 #endif28 29     scanf("%d", &case_n);30     for (a=0; a<case_n; ++a) {31         scanf("%d %d %d", &n, &t, &m);32         rear[0] = rear[1] = 0;33         front[0] = front[1] = 0;34         for (i=1; i<=m; ++i) {35             scanf("%d %s", &k, s);36             if (s[0] == l)37                 j = 0;38             else39                 j = 1;40             Q[j][rear[j]].i = i;41             Q[j][rear[j]].t = k;42             rear[j]++;43         }44         Q[0][rear[0]].t = INF;45         Q[1][rear[1]].t = INF;46         d = 0;47         int ans = 0;48         while (front[0]<rear[0] || front[1]<rear[1]) {49             if (Q[d][front[d]].t>ans && Q[!d][front[!d]].t<=ans) {50                 ans += t;51                 d = !d;52             } else if ((Q[d][front[d]].t>Q[!d][front[!d]].t || front[d]>=rear[d]) && Q[!d][front[!d]].t>ans) {53                 ans = Q[!d][front[!d]].t + t;54                 d = !d;55             }56             if (ans < Q[d][front[d]].t)57                 ans = Q[d][front[d]].t;58             j = 0;59             i = front[d];60             while (j<n && i<rear[d] && Q[d][i].t<=ans) {61                 buf[Q[d][i].i] = ans + t;62                 ++j;63                 ++i;64             }65             ans += t;66             front[d] = i;67             d = !d;68         }69         if (a)70             printf("\n");71         for (i=1; i<=m; ++i)72             printf("%d\n", buf[i]);73     }74 75     return 0;76 }

 

【HDOJ】1406 Ferry Loading III