首页 > ACM题库 > HDU-杭电 > HDU 3219-Jammed Traffic-模拟-[解题报告]HOJ
2014
03-07

HDU 3219-Jammed Traffic-模拟-[解题报告]HOJ

Jammed Traffic

问题描述 :

Finally, YY graduated from a little known university and got employed by a small company, with great effort. The job is interesting, well paid and nice in many
aspects, except for the company is a little far from home. So YY has to take bus to work every day early in the morning, and prays for no traffic jams along the road.

The route of the bus is fixed. It goes past N+1 landmarks one by one, the first of which is the bus-stop where YY gets on the bus, and the last is the company
where he should get off. If traffic jams do not occur, the time consumed to go between landmarks is also fixed ― Ti minutes from ith landmark to (i+1)th
landmark (1≤i≤N). However, if a traffic jam is encountered, things are different. After having been late for many times (and luckily enough not been fired by his
boss & girlfriend LMY), YY has discovered that the road between two consecutive landmarks will be jammed only in a fixed time period in a day. If the bus is
between ith landmark and (i+1)th landmark (excluding at the two landmarks themselves) and encounters a traffic jam, additional Di minutes are needed to
get to (i+1)th landmark.

Given the time YY gets on the bus and the time his company start to work, could he reach the company in time?

输入:

For each test case, the first line contains only one integer N. (1≤N≤100)
Then N lines follow. The ith line of which describes the road between ith landmark and (i+1)th landmark. Two integers comes first, Ti and Di (1≤Ti , Di≤60), indicating
the basic time consumption and additional time consumption with traffic jam for the bus to go between the two landmarks, in minutes. A pair of time Si and Ei follows,
in HH:MM format (24 hours), indicating the starting and ending time of traffic jam between the two landmarks. Si is always strictly earlier than Ei, and they are always
in the same day.

The last line contains the time when YY gets on the bus and the time when the company starts to work, in HH:MM format (24 hours). He must arrive at the company
strictly before it starts to work, or he is late.

All times are in the same day.
Input end with N=0.

输出:

For each test case, the first line contains only one integer N. (1≤N≤100)
Then N lines follow. The ith line of which describes the road between ith landmark and (i+1)th landmark. Two integers comes first, Ti and Di (1≤Ti , Di≤60), indicating
the basic time consumption and additional time consumption with traffic jam for the bus to go between the two landmarks, in minutes. A pair of time Si and Ei follows,
in HH:MM format (24 hours), indicating the starting and ending time of traffic jam between the two landmarks. Si is always strictly earlier than Ei, and they are always
in the same day.

The last line contains the time when YY gets on the bus and the time when the company starts to work, in HH:MM format (24 hours). He must arrive at the company
strictly before it starts to work, or he is late.

All times are in the same day.
Input end with N=0.

样例输入:

1
10 20 07:30 08:00
07:20 07:35
1
10 20 07:30 08:00
07:21 07:51
1
1 1 12:00 12:30
23:59 00:01
0

样例输出:

Lucky YY!
Poor YY!
Poor YY!
Hint
In the first test case, the bus starts at 07:20 and arrives at the company at 07:30, just avoids to be blocked by the traffic jam. In the second test case, the bus start at 07:21 and encounters traffic jam at 07:30 when it is still on the way to the company. So additional 20 minutes are needed, and it arrives at the company at 07:51. So poor YY is just late, because he doesn’t reach the company before 07:51, when it starts to work. In the third test case, the bus arrives at the company at 00:00 in the second day, so he is considered to be late for almost one entire day.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3219

题目意思:某人去上班,上班的路上分为n段每段都有标志,也就是总共n+1处标志,第一个标志是他上车的地方,第n+1个标志就是他工作的地方也就是目的地。在每某段 i 中给定某个时间段,在这段时间里为交通阻塞期,正常通过第 i 段需花费 a[i]的时间,若赶上阻塞期则需多花费b[i]的时间。

告诉你每段的情况,问你后他能否准时到达工作地。

这个题有几个注意事项:在阻塞期的开始和结束时间为开区间,到达的时间为闭区间,另外这里的时间都为一天内的情况,若时间大于24点说明晚了一天。

代码如下:


#include <iostream>
#include <cstdio>

using namespace std;


int zhengc[101],yanchi[101];
int times[101],timee[101];
int ts,te;

int main(){
	int n;
	while(scanf("%d",&n)&&n){
		int a,b,c,d,i;
		for(i=1;i<=n;i++){
			scanf("%d%d",&zhengc[i],&yanchi[i]);
			yanchi[i]+=zhengc[i];
			scanf("%d:%d %d:%d",&a,&b,&c,&d);
			times[i]=a*60+b;
			timee[i]=c*60+d;
		}
		scanf("%d:%d %d:%d",&a,&b,&c,&d);
		ts=a*60+b;
		te=c*60+d;
		bool mark=true;
		int tt;
		for(i=1;i<=n;i++){
			tt=ts+zhengc[i];
			if(tt>=1440){
				mark=false;
				break;
			}
            if(tt<=times[i] || ts>=timee[i]){
				ts+=zhengc[i];
				if(ts>=te || ts>=1440){
					mark=false;
					break;
				}
			}else{
				ts+=yanchi[i];
				if(ts>=te || ts>=1440){
					mark=false;
					break;
				}
			}
		}
		if(mark){
			if(ts<te){
				printf("Lucky YY!\n");
			}else{
				printf("Poor YY!\n");
			}
		}else{
			printf("Poor YY!\n");
		}
	}
	return 0;
}

参考:http://blog.csdn.net/iaccepted/article/details/6740860


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  4. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  5. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.