D - Access System（排序）ZOJ

原题链接： Access System

测试样例

Sample Input
3
2 1
12:30:00
12:30:01
5 15
17:00:00
17:00:15
17:00:06
17:01:00
17:00:14
3 5
12:00:09
12:00:05
12:00:00
Sample Output
2
1 2
3
1 2 4
2
2 3

题意： 当门是关闭的时候学生进入需要用卡才能打开，在此后的L秒内门不会锁，即其余学生可以不用卡进入。给出每个学生到达的时间段，你需要找出有多少个人需要用卡进入。

解题思路： 解决这道题的关键就是要知道怎么处理数据与自定义排序。对于输入的标准格式，我们可以用一个字符型变量来存储中间的冒号，而将对应的时分秒放入一个结构体变量存储。 解决了这一步我们当然是要对这到达时间进行排序，故我们需要自己写一个比较函数，这个如果不会的话请翻阅相关文章。注意我们排序的时候是不能改变学生编号的，故我们这里有个细节是用一个辅助数组存储学生编号，再对这个辅助数组进行排序。之后就直接遍历统计即可。具体看AC代码。

AC代码

/*
*邮箱：[e-mail]
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e5;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//

struct Time{
	int h,m,s;
};
Time times[maxn];
bool cmp(int i,int j){
	if(times[i].h==times[j].h){
		if(times[i].m==times[j].m){
			return times[i].s<times[j].s;
		}
		else{
			return times[i].m<times[j].m;
		}
	}
	else{
		return times[i].h<times[j].h;
	}
}
int calculate(Time &a,Time &b){
	int h=a.h-b.h;
	int m=a.m-b.m;
	int s=a.s-b.s;
	return h*3600+m*60+s;
}
int cnt[maxn];
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	int t,n,l;
	char op;
	while(cin>>t){
		while(t--){
			cin>>n>>l;
			rep(i,1,n){
				cin>>times[i].h>>op>>times[i].m>>op>>times[i].s;
				cnt[i]=i;
			}
			sort(cnt+1,cnt+1+n,cmp);
			Time temp;
			temp.h=times[cnt[1]].h,temp.m=times[cnt[1]].m,temp.s=times[cnt[1]].s;
			vector<int> result;
			result.push_back(cnt[1]);
			rep(i,2,n){
				if(calculate(times[cnt[i]],temp)>=l){
					result.push_back(cnt[i]);
					temp.h=times[cnt[i]].h,temp.m=times[cnt[i]].m,temp.s=times[cnt[i]].s;
				}
			}
			int len=result.size();
			sort(result.begin(),result.end());
			cout<<len<<endl;
			rep(i,0,len-1){
				cout<<result[i];
				if(i!=len-1){
					cout<<" ";
				}
			}
			cout<<endl;
		}
	}
	return 0;
}