题目集9：7 无接触水龙头

新冠疫情席卷全球已经两年有余，每个人都在为战胜这场灾难贡献自己的力量，希望这场灾难早日过去。

为了减少公共场所人与人间接接触的概率，大学生小D发明了一款自动洗手器。这款机器基于红外线感应的原理，用户只需要把手伸到水龙头下方即可自动出水，不需要再动手操作开关，这样就减少了病毒残留在开关处传播的风险。

小D这款设备的运行逻辑是：当设备的出水倒计时不为0时，水龙头会出水，并且倒计时随着时间减少。每当红外线感应器感应到有人伸手，就会将出水倒计时重置为t秒，出水倒计时为0秒时停止出水。

现在小D给了你感应器的记录列表，里面记录了在什么时间感应到了用户伸手，想请你计算在设备的运行过程中，总共流了多少秒的水。这样以便他对设备继续更新。

第一行两个整数n,t (1≤n≤105,1≤t≤109)分别表示记录的条数和仪器每次出水的时间。
其后n行，每行是一个时间，表示在该时刻感应到了用户使用该仪器。
时间的格式是 yyyy-MM-dd HH:mm:ss。其中y是年份,M是月份,d是日期,H是小时,m是分钟,s是秒数。 比如: 2022-05-08 01:12:34，表示:2022年5月8号1点12分34秒。
数据保证年份是2020年-2022年。
不保证时间的顺序。

输出一行一个整数，表示水龙头在运行过程中总的出水秒数。

2 10
2020-01-01 12:00:09
2020-01-01 12:00:00

19

设水龙头一次留的时间为n

1. 把水龙头的记录的时间进行排序
2. 计算两个相邻时间的时间差
   1. 如果大于n，取n
   2. 如果小于n，就取这个数
3. 最后再加上一个n，因为最后一次记录的时候会流n秒

又是超时，我真的快吐了。

#include
#include
void bubble_sort(int arr[], int len);
int main()
{
	int n, unit_time, yy, MM, dd, hh, mm, ss;
	int time[100000] = { 0 }, sum = 0, arr[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
	scanf("%d %d", &n, &unit_time);
	for (int i = 0; i < n; i++)
	{
		scanf("%d-%d-%d %d:%d:%d", &yy, &MM, &dd, &hh, &mm, &ss);
		if (yy-2020 == 0)
		{
			time[i] += 24 * 3600;
			for (int j = 1; j < MM; j++)
			{
				time[i] += arr[j] * 24 * 3600;
			}
			time[i] += dd * 24 * 3600 + hh * 3600 + mm * 60 + ss;
		}
		else
		{
			if (yy-2020 ==1)
			{
				time[i] += 366 * 24 * 3600;
				for (int j = 1; j < MM; j++)
				{
					time[i] += arr[j] * 24 * 3600;
				}
				time[i] += dd * 24 * 3600 + hh * 3600 + mm * 60 + ss;
			}
			else
			{
				time[i] += (366 + 365) * 24 * 3600;
				for (int j = 1; j < MM; j++)
				{
					time[i] += arr[j] * 24 * 3600;
				}
				time[i] += dd * 24 * 3600 + hh * 3600 + mm * 60 + ss;
			}
		}
	}
	bubble_sort(time, n);
	for (int i = 0; i < n-1; i++)
	{
		if (time[i+1]- time[i] < unit_time)
		{
			sum += time[i + 1] - time[i];
		}
		else
		{
			sum += unit_time;
		}
	}
	sum += unit_time;
	printf("%d", sum);
	return 0;
}
void bubble_sort(int arr[], int len) {
	int i, j, temp;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}

听取了别人的意见：使用了快排。这次没有超时。同时又改良了一下对于时间的计算（这一步参考了别人的代码）

#include
int quick_sort(int* a, int low, int high);
int main()
{
	int n, unit_time;
	int time[100000] = { 0 }, sum = 0;
	int len[3] = { 0, 366, 731 };
	int mon[3][13] = { 
		{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
		{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
		{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
	};

	scanf("%d %d", &n, &unit_time);
	for (int i = 0; i < n; i++)
	{
		int year, m, d, hh, mm, ss;
		scanf("%d-%d-%d %d:%d:%d", &year, &m, &d, &hh, &mm, &ss);
		time[i] = len[year - 2020] * 24 * 3600;
		for (int j = 1; j < m; j++)
			time[i] += mon[year - 2020][j] * 24 * 3600;
		time[i] += (d - 1) * 24 * 3600;
		time[i] += hh * 3600 + mm * 60 + ss;

	}
	quick_sort(time, 0, n - 1);
	for (int i = 0; i < n - 1; i++)
	{
		if (time[i + 1] - time[i] < unit_time)
		{
			sum += time[i + 1] - time[i];
		}
		else
		{
			sum += unit_time;
		}
	}
	sum += unit_time;
	printf("%d", sum);
	return 0;
}
int quick_sort(int* a, int low, int high)
{
	int i = low;	//第一位
	int j = high;	//最后一位
	int key = a[i]; //将第一个数作为基准值-- 先找到一个基准值

	while (i < j)
	{
		while (i < j && a[j] >= key)
		{
			j--;
		}
		a[i] = a[j];

		while (i < j && a[i] <= key)
		{
			i++;
		}
		a[j] = a[i];
	}
	a[i] = key;
	if (i - 1 > low)
	{
		quick_sort(a, low, i - 1);
	}

	if (i + 1 < high)
	{
		quick_sort(a, i + 1, high);
	}
	return 0;
}