PAT A1006 Sign In and Sign Out

题目链接

我的解法：先排序，再取值

解题思路：分别对前到时间和签退时间进行排序，最后取每一次排序的第一个。注意比较函数的写法，不相等的情况下直接返回一个不等式！

#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn=10001;
using namespace std;
struct Time{
	int h,m,s;
};
struct Stu{
	char id[16];
	Time in,out;
}stu[maxn];
bool cmp1(const Stu& a,const Stu& b){
	if(a.in.h!=b.in.h) return a.in.h<b.in.h;
	if(a.in.m!=b.in.m) return a.in.m<b.in.m;
	return a.in.s<b.in.s;
}
bool cmp2(const Stu& a,const Stu& b){
	if(a.out.h!=b.out.h) return a.out.h>b.out.h;
	if(a.out.m!=b.out.m) return a.out.m>b.out.m;
	return a.out.s>b.out.s;
}
int main(){
	int n,h1,h2,m1,m2,s1,s2;
	char id[16];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s %d:%d:%d %d:%d:%d",stu[i].id,&h1,&m1,&s1,&h2,&m2,&s2);
		stu[i].in.h=h1;stu[i].in.m=m1;stu[i].in.s=s1;
		stu[i].out.h=h2;stu[i].out.m=m2;stu[i].out.s=s2;
	}
	sort(stu,stu+n,cmp1);
	printf("%s ",stu[0].id);
	sort(stu,stu+n,cmp2);
	printf("%s",stu[0].id);	
	return 0;
}

算法笔记解法：边读取边比较！

这个方法比我的解法效率要高，但耗时一样！方法是直接定义三个结构体类型变量，一个中间变量，一个是签到时间，一个签退时间。比较函数只写一个，当返回false的时候即为取反！

#include <cstdio>
#include <cstring>

struct Stu{
	char id[16];
	int h,m,s;
}temp,in,out;
bool greater(const Stu& a,const Stu& b){
	if(a.h!=b.h) return a.h>b.h;
	if(a.m!=b.m) return a.m>b.m;
	return a.s>b.s;
}

int main(){
	int n,h1,h2,m1,m2,s1,s2;
	//初始化
	in.h=24,in.m=60,in.s=60;
	out.h=0,out.m=0,out.s=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s %d:%d:%d",temp.id,&temp.h,&temp.m,&temp.s);
		if(greater(temp,in)==false)	in=temp;
		scanf("%d:%d:%d",&temp.h,&temp.m,&temp.s);
		if(greater(temp,out)==true) out=temp;		
	}
	printf("%s %s",in.id,out.id);	
	return 0;
}