首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。