1006.Sign In and Sign Out

2017-10-28

英文描述

Sign In and Sign Out (25)
At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.
Input Specification:
Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:
ID_number Sign_in_time Sign_out_time
where times are given in the format HH:MM:SS, and ID number is a string with no more than 15 characters.
Output Specification:
For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.
Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.
Sample Input:
3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40
Sample Output:
SC3021234 CS301133

中文描述

登录和退出
在每一天开始的时候，第一个来的人将要打开计算机教室门上的锁，最后一个离开的人将要锁住计算机教室的门。给出一个进门与出门的记录，你要找出那天中谁把门打开了和谁把门锁住了。
输入规格：
每一个输入文件包含一个测试用例。每个用例包含了一天的记录。这个用例的第一行是一个正整数M，代表一共有多少条记录，接着是M行，每一行的格式为：
身份号码进入时间出去时间
时间的格式为：小时：分钟：秒数，身份号码是一个不超过15个字符的字符串。
输出规格：
对于每一个测试用例，在一行内输出这一天中开门和关门的人的身份号码，两个身份号码之间需要被一个空格间隔开来。
注意：开门和关门的人的记录一定是存在的。每个人的开门时间必须早于关门时间，没有两个人的开门或者关门时间是相同的。
样例输入:
3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40
样例输出:
SC3021234 CS301133

分析与解题

找出最早的登录时间和最晚的退出时间。使用一个二维字符数组来存储这些内容，之后从这个字符数组中解析出ID和登录时间和退出时间，接着对这些时间进行选择，选择最早的登录时间和最晚的退出时间取其ID。
想起来挺简单，但写起来是有些复杂的，后来看到strcmp函数可以直接进行判断，用strcmp函数比较简单，其实在输入的时候也是可以进行判断的，关于数据结构和scanf函数的应用，ZJU那个算法写的很不错，以后会多借鉴一下那些技巧。自己在思考使用函数来存储，以及如何去接受来自文件的输入时，策略总是太差，原因也就是对那么函数不太熟悉。比如scanf是以空格和回车结束的，gets是以回车作为结束的。

C语言实现

#include<stdio.h>
#include<string.h>
char info[1000][1000];
int M;
char first[9] = {'9', '9', ':', '9', '9', ':', '9', '9'};
char *fst = first;
int fs = 0;
char last[9] = {'0', '0', ':', '0', '0', ':', '0', '0'};
int ls = 0;
char *l = last;
void input()
{
	scanf("%d", &M);
	int i = 1;
	getchar();
	while(i <= M)
	{
		gets(info[i]);
		i++;
	}
}
void calc(int f)
{
	int i = 1;
	while(i <= M)
	{
		char (*p) = info[i];
		while(*p)
		{
			if(*p == ' ')
			{
				fst = first;
				char *cin = p + 1;
				char *in = p + 1;
				while(*in)
				{
					if(f == 1)
					{
						//sign out time
						if(*in == ' ')
						{
							l = last;
							char *cout = in + 1;
							char *out = in + 1;
							while(*out)
							{
								//seek last person
								if(*l < *out)
								{
									//out copy to last
									memcpy(last, cout, 9);	
									//remark last subscript
									ls = i;
									break;
								}
								else if(*l == *out)
								{
									l++;
									out++;
								}
								else
									break;
							}
						}
					}
					else
					{
						//seek first person
							
						if(*fst > *in)
						{
							//out copy to last
							memcpy(first, cin, 8);	
							first[8] = '\n';
							//remark last subscript
							fs = i;
						}
						else if(*fst == *in)
						{
							fst++;
						}
						else
							break;
						if(*in == ' ')
							break;
					}
					in++;
				}
				break;
			}
			p++;
		}
		i++;
	}
}
void output()
{
	fst = info[fs];
	while(*fst)
	{
		if(*fst == ' ')
			break;
		printf("%c", *fst);
		fst++;
	}
	putchar(' ');
	l = info[ls];
	while(*l)
	{
		if(*l == ' ')
			break;
		printf("%c", *l);
		l++;
	}
}
int main()
{
	input();
	calc(1);
	calc(0);
	output();
	return 0;
}

测试链接

click me