24. 解密犯罪时间

题目描述

警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如“HH:MM”表示的时刻。根据警察和线人的约定，为了隐蔽，该时间是修改过的，解密规则为:利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。每个出现数字都可以被无限次使用。

输入描述

形如HH:SS字符串，表示原始输入

输出描述

形如HH:SS的字符串，表示推理处理的犯罪时间。

备注

1.可以保证现任给定的字符串一定是合法的。

例如，“01:35”和“11:08”是合法的，“1:35”和“11:8”是不合法的

2.最近的时刻可能在第二天。

用例

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.警察在侦破一个案件的时候，得到了线人给出的可能犯罪时间，形如“HH：MM”表示的时刻。

2.根据警察和线人的约定，为了隐蔽，该时间是修改过的，解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，该时间为可能的犯罪时间。每个出现数字都可以被无限次使用。

3.输入描述：形如HH：SS字符串，表示原始输入。

4.输出描述：形如HH：SS的字符串，表示推理处理的犯罪事件。

5.备注:（1）可以保证线人给定的字符串一定是合法的。

（2）最近的时刻可能在第二天。

二、解题思路

1.首先要看懂题目，题目的意思是说使用输入中给出的数字，构造一个距离输入时间最近的下一个时间

2.这个时间有可能是第二天。

3.首先明确HH的有效范围是00-23，SS的有效范围是00-59,

也就是说第一位数字可以是0，1，2，第二位数字在第一位数字是0和1的时候可以是0，1，2，3，4，5，6，7，8，9，在第一位数字是2的时候只能是0，1，2，3

第三位数字可以是0，1，2，3，4，5，第四位数字可以是0，1，2，3，4，5，6，7，8，9

4.所以我们可以从最后一位开始，比如时间是16：54分，我们查找1，6，5中有没有比4更大的中的数字最小的，找到了5，6，其中最小的是5所以我们下一个时间是16：55分

5.如果遇到12：34这种情况呢？1，2，3都比4小，那么我们就比较倒数第二位数字，我们要找到1，2，4中比三大的最小的数字，4刚好比3大，所以我们的下一个时间是12：4X分，X寻找1，2，3，4中最小的补充上就可以了，1最小，所以我们下一个时间是12：41分

6.如果是12：33分呢？后两位相同，且1，2都比3小，这个时候我们需要比较倒数第三位数字，发现3比2大，于是我们的时间变成了13：XX，XX选择1，2，3中比较小的补充上，于是我们的时间变成了13：11分

7.如果时间是13：33分呢？后三位都相同，1比3小，第一位数字又不能变成3。

这种情况下我们考虑下一个时间是下一天，所以我们比较的时间变成了00：00，我们直接用最小的数字补充上就行了11：11

因为第一个数字肯定是0，1，2，所以这三个数字可以填充在任何一个位置，而其他符合的数字一定比2小，如果在第一个数字后面有比第一个数字小的那么我们最近的时间就不需要是下一天了（比如21：59分，这里有比2小的1，但是因为在2后面，所以我们的下一个时间直接是22：11分就可以了）

8.所以我们只需要从后往前，找到比当前数字大的合法的数字是否出现在四个数字中，如果可以匹配上，那么剩下的后面的几位就填充上四个数中最小的数字就可以了

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int findminmatch(int a, int b, int c, int start, int end) {bool ba = false;bool bb = false;bool bc = false;if(a > start && a <= end) {ba =true;// printf("a > start and a <= end %d > %d and %d <= %d\n", a, start, a, end);}if(b > start && b <= end) {bb = true;// printf("b > start and b <= end %d > %d and %d <= %d\n", b, start, b, end);}if(c > start && c <= end) {bc = true;// printf("c > start and c <= end %d > %d and %d <= %d\n", c, start, c, end);}int minnum = 10;if(ba) {if(a < minnum) minnum = a;//printf("minnum is a = %d\n", a);}if(bb) {//printf("minnum is = %d\n", minnum);if(b < minnum) minnum = b;//printf("minnum is b = %d\n", minnum);}if(bc) {//printf("minnum is = %d\n", minnum);if(c < minnum) minnum = c;//printf("minnum is c = %d\n", minnum);}if(minnum == 10) return -1;else return minnum;
}int findmin(int a, int b, int c, int d) {if(a <= b && a <= c && a <= d) return a;if(b <= a && b <= c && b <= d) return b;if(c <= a && c <= b && c <= d) return c;return d;
}int main() {char cH1,cH2,cM1,cM2;int H3,H4,M3,M4;scanf("%c%c:%c%c", &cH1, &cH2, &cM1, &cM2);// 从最后一位开始查找，int H1 = cH1 - '0', H2 = cH2 - '0', M1 = cM1 - '0', M2 = cM2 - '0';int min = findmin(H1, H2, M1, M2);int last = findminmatch(H1 , H2, M1, M2, 9);if(last != -1) {H3 = H1;H4 = H2;M3 = M1;M4 = last;// printf("last test\n");} else {int secondl = findminmatch(H1, H2, M2, M1, 5);if(secondl != -1) {H3 = H1;H4 = H2;M3 = secondl;M4 = min;} else {int thirdl;if(H1 == 0 || H1 == 1) {thirdl = findminmatch(H1, M1, M2, H2, 9);} else {thirdl = findminmatch(H1, M1, M2, H2, 3);}if(thirdl != -1) {H3 = H1;H4 = thirdl;M3 = min;M4 = min;} else {int first = findminmatch(H2, M1, M2, H1, 2);if(first != -1) {H3 = first;H4 = min;M3 = min;M4 = min;} else {H3 = min;H4 = min;M3 = min;M4 = min;}}}}printf("%d%d:%d%d\n",H3,H4,M3,M4);return 0;
}