当前位置：首页 > article >正文

机试题——最大时间

article 2024/12/26 9:39:04

题目描述

给定一个数组，里面有 6 个整数，求这个数组能够表示的最大 24 进制的时间是多少，输出这个时间，无法表示输出 invalid。

在 24 进制时间格式下，时间由小时、分钟和秒数组成，时间格式为 hh:mm:ss。要求：

小时（hh）必须由两位数字组成，且小于 24。
分钟（mm）和秒数（ss）必须由两位数字组成，且小于 60。
给定六个数字，使用其中的每个数字一次，组成一个最大可能的有效时间。

如果无法组成有效时间，输出 invalid。

输入描述

输入为一个包含六个整数的数组。

数组长度为 6，不需要考虑其它长度，元素值为 0 或正整数。
每个数字只能使用一次。

输出描述

输出一个 24 进制格式的时间 hh:mm:ss，如果无法组成有效时间，则输出 invalid。

用例输入

0 2 3 0 5 6

23:56:00

1 2 3 4 5 6

23:56:41

9 9 9 9 9 9

invalid

解题思路

需要从六个给定的数字中选取出有效的小时、分钟和秒数，构成一个最大可能的时间。具体的步骤如下：

有效时间条件：
- 小时（hh）的范围是 0 到 23；
- 分钟（mm）和秒数（ss）的范围是 0 到 59。
算法：
- 使用回溯法（DFS）枚举所有可能的时间组合。
- 通过递归在六个数字中选取数字来组成小时、分钟和秒数部分。每个数字只能使用一次。
- 对于每次生成的时间，检查其是否有效。如果有效，则记录下来并比较最大值。
具体步骤：
- 通过 DFS 遍历所有排列，尝试从六个数字中选择两个数字组成小时部分，再从剩下的数字中选择两个数字组成分钟部分，最后选择剩余的两个数字组成秒钟部分。
- 生成的时间字符串格式为 hh:mm:ss，如果没有有效的时间则输出 invalid。

复杂度是O(6!)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<stack>
using namespace std;

vector<int> arr(6); //输入数据
vector<int> used(6, 0);//标记是否使用arr[i]
vector<int> result(6, -1); //储存时间的时分秒

// 检查时间是否合法
bool isValidTime(int hour, int minute, int second) {
    return hour < 24 && minute < 60 && second < 60;
}

// 将数字转换为格式化的时间字符串
string formatTime(int hour, int minute, int second) {
    return to_string(hour) + ":" + (minute < 10 ? "0" : "") + 
        to_string(minute) + ":" + (second < 10 ? "0" : "") + to_string(second);
}

// 递归DFS，枚举所有可能的时间组合
void dfs(int step, vector<int>& time) {
    // 如果已经完成了小时、分钟和秒数的组合
    if (step == 6) {
        int hour = time[0] * 10 + time[1];
        int minute = time[2] * 10 + time[3];
        int second = time[4] * 10 + time[5];

        if (isValidTime(hour, minute, second)) {
            //判断合法直接比合法的时间 vector（默认就是数值的大小） 
            if (result[0]==-1 || time > result) {
                result = time;
            }
        }
        return;
    }
    // 递归选取数字
    for (int i = 0; i < 6; ++i) {
        if (used[i]) continue;
        used[i] = true;
        time[step] = arr[i];
        // 递归继续
        dfs(step + 1, time);
        used[i] = false; // 回溯，取消选择
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i < 6; ++i) {
        cin >> arr[i];
    }
    vector<int> time(6, -1);  // 保存小时、分钟、秒数的部分
    dfs(0, time);
    if (result[0] == -1) {
        cout << "invalid\n";
    }
    else {
        //组合输出
        int hour = result[0] * 10 + result[1];
        int minute = result[2] * 10 + result[3];
        int second = result[4] * 10 + result[5];
        cout << formatTime(hour, minute, second) << "\n";
    }
    return 0;
}