【CodeForces-816A】Karen and Morning【进制+暴力+栈】

【CodeForces-816A】Karen and Morning【进制+暴力+栈】

问题链接:https://vjudge.net/problem/CodeForces-816A

题目描述:

Karen is getting ready for a new school day!

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.

Input:

The first and only line of input contains a single string in the format hh:mm (00 ≤ hh  ≤ 2300 ≤  mm  ≤ 59).

Output:

Output a single integer on a line by itself, the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome.

 

Solution:

这道题十分有趣。Karen认为在“回文时间”起床十分幸运,于是,程序要求,对于给出的她要睡觉的时间,找到这个时间距离最近的“回文(Palindrome)时间”间隔多少分钟。【解释:这题所谓“回文时间”,如05:50,它是回文的。而如05:23,它不是回文的,即两边数值是不对称的】

第一点:关于时间(年月日时)的处理十分常见,时间可以看成一种特殊的进制,在这里,我们可以注意到,分钟数是以60为进制的,每60分钟,就可以进位1到小时位上。反过来,1小时就相当于60分钟,那么我们可以把每一时刻都转化到唯一的分钟数上,如05:50就等于5 * 60 + 50 = 350分钟。

第二点:暴力(Brute Force)。暴力枚举在数据范围很小的情况下通常是一种很好的解决方案,这道题注意到时间的取值范围是00:00 ~ 23:59,按照“第一点”所提的方法,这里可以转化为24 * 60 + 0个不同的分钟数,直接尝试每个分钟数所对应的时间是否构成“回文时间”就好。

第三点:用栈判断回文。栈是一种很常用的数据结构,可以想象它是一个衣柜,每次我们只能把新的衣服放到最顶部,而取衣服的时候也只能从最顶部取。考虑时间05:50,我们先处理小时部分,即05,我们把个位的5先放入栈中,再把十位的0压入栈中,如下图。

接着,我们考虑分钟部分的50,我们依然先考虑它的个位(即0),我们将这个与上图栈顶的数比较,发现0 = 0,很好,二者一样;于是我们将这个栈顶的0扔掉,接着我们用十位(即5)比较现在的栈顶(刚刚栈顶的0扔出去了,于是现在的栈顶是5),发现5 = 5,很好,又一样,因此我们的任务完成了,发现这个就是“回文时间”。

我们发现,这里使用栈这种数据结构,为我们提供了逆序,因为我们知道,如果这个串是回文的,它的两边一定是对称的,那么我们如果把一边的顺序颠倒一下,二者就应该完全一样了,如果发现不一样,就说明不是回文。

#include <stdio.h>

int stack[2];
int isPalindrome(int h, int m) {
    int pos = 0;
    int cx = 2;
    while (cx--) {
        stack[pos++] = h % 10;
        h /= 10;
    }
    while(pos--) {
        if (stack[pos] != m % 10) return 0;
        m /= 10;
    }
    return 1;
}

int main(void) {
    int h, m;
    int lim = 24 * 60;
    scanf("%d:%d", &h, &m);
    for (int cnt = h * 60 + m; true; cnt++) {
        if (cnt >= lim) cnt %= lim;
        if (isPalindrome(cnt / 60, cnt % 60)) {
            printf("%d\n", ((cnt - h * 60 - m) % lim + lim) % lim);
            break;
        }
    }
    return 0;
}