题目描述

华为商城举办了一个促销活动，如果某顾客在某一秒内最早下单的顾客（可能是多个人），则可以获取免单。编程计算有多少顾客可以获取免单。

输入描述

• 整数 n，表示顾客的数量。
• 接下来的 n 行数据，每一行表示一位顾客的下单时间，以（年-月-日 时-分-秒.毫秒）形式给出。

输出描述

• 输出一个整数，表示有多少顾客可以获取免单。

解题思路

1. 时间排序：将所有下单时间进行排序，确保按时间先后排列。
2. 确定免单顾客：
   • 遍历排序后的时间列表，记录每一秒的最早下单时间。
   • 对于单位秒里最早的相同时间的订单，都免单。

复杂度分析

• 时间复杂度：O(n log n)，主要体现在排序步骤。
• 空间复杂度：O(n)，用于存储顾客的下单时间。

代码实现

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n; // 读取顾客数量

    getchar(); // 读取换行符

    vector<string> times(n); // 存储下单时间的字符串数组
    for (int i = 0; i < n; i++) {
        getline(cin, times[i]); // 逐行读取每位顾客的下单时间
    }

    // 按时间排序
    sort(times.begin(), times.end());

    int num = 1; // 免单顾客计数，初始化为1，表示第一个顾客可以免单

    string lastTime = times[0]; // 记录上一个订单的完整时间
    string lastSecond = lastTime.substr(0, 19); // 获取上一个订单的前19个字符（年-月-日 时-分-秒）

    // 遍历从第二个顾客开始的时间
    for (int i = 1; i < n; i++) {
        string curTime = times[i]; // 当前订单的时间
        string curSecond = curTime.substr(0, 19); // 获取当前订单的前19个字符

        // 如果当前订单时间与上一个订单相同，或者当前秒与上一个秒不同
        if (curTime == lastTime || curSecond != lastSecond) {
            num++; // 增加免单顾客计数
            lastTime = curTime; // 更新上一个订单时间
            lastSecond = curSecond; // 更新上一个秒
        }
    }

    cout << num << endl; // 输出免单顾客的数量

    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取顾客数量
        scanner.nextLine(); // 读取换行符

        String[] times = new String[n]; // 存储下单时间的字符串数组
        for (int i = 0; i < n; i++) {
            times[i] = scanner.nextLine(); // 逐行读取每位顾客的下单时间
        }

        // 按时间排序
        Arrays.sort(times);

        int num = 1; // 免单顾客计数，初始化为1，表示第一个顾客可以免单

        String lastTime = times[0]; // 记录上一个订单的完整时间
        String lastSecond = lastTime.substring(0, 19); // 获取上一个订单的前19个字符（年-月-日 时-分-秒）

        // 遍历从第二个顾客开始的时间
        for (int i = 1; i < n; i++) {
            String curTime = times[i]; // 当前订单的时间
            String curSecond = curTime.substring(0, 19); // 获取当前订单的前19个字符

            // 如果当前订单时间与上一个订单相同，或者当前秒与上一个秒不同
            if (curTime.equals(lastTime) || !curSecond.equals(lastSecond)) {
                num++; // 增加免单顾客计数
                lastTime = curTime; // 更新上一个订单时间
                lastSecond = curSecond; // 更新上一个秒
            }
        }

        System.out.println(num); // 输出免单顾客的数量
    }
}

Python

def main():
    n = int(input())  # 读取顾客数量
    times = [input().strip() for _ in range(n)]  # 存储下单时间的字符串列表

    # 按时间排序
    times.sort()

    num = 1  # 免单顾客计数，初始化为1，表示第一个顾客可以免单

    lastTime = times[0]  # 记录上一个订单的完整时间
    lastSecond = lastTime[:19]  # 获取上一个订单的前19个字符（年-月-日 时-分-秒）

    # 遍历从第二个顾客开始的时间
    for i in range(1, n):
        curTime = times[i]  # 当前订单的时间
        curSecond = curTime[:19]  # 获取当前订单的前19个字符

        # 如果当前订单时间与上一个订单相同，或者当前秒与上一个秒不同
        if curTime == lastTime or curSecond != lastSecond:
            num += 1  # 增加免单顾客计数
            lastTime = curTime  # 更新上一个订单时间
            lastSecond = curSecond  # 更新上一个秒

    print(num)  # 输出免单顾客的数量

if __name__ == "__main__":
    main()

题目描述

华为商城举办了一个促销活动，如果某顾客是某一秒内最早时刻下单的顾客（可能是多个人），则可以获取免单。

请你编程计算有多少顾客可以获取免单。

输入描述

输入为 $n$ 行数据，每一行表示一位顾客的下单时间以（年-月-日 时-分-秒.毫秒）形式给出。

yyyy-MM-dd HH:mm:ss.fff

$0 < n < 50000$

$2000 < yyyy < 2020$

$0 < MM ≤ 12$

$0 < dd ≤ 28$

$0 ≤ HH ≤ 23$

$0 ≤ mm ≤ 59$

$0 ≤ ss ≤ 59$

$0 ≤ fff ≤ 999$

所有输入保证合法

输出描述

输出一个整数，表示有多少顾客可以获取免单。

样例1

输入

3
2019-01-01 00:00:00.001
2019-01-01 00:00:00.002
2019-01-01 00:00:00.003

输出

1

说明

样例 $1$ 中，三个订单都是同一秒内下单，只有第一个订单最早下单，可以免单。

样例2

输入

3
2019-01-01 08:59:00.123
2019-01-01 08:59:00.123
2018-12-28 10:08:00.999

输出

3

说明 样例 $2$ 中，前两个订单是同一秒内同一时刻（也是最早）下单，都可免单，第三个订单是当前秒内唯一一个订单（也是最早），也可免单。

样例3

输入

5
2019-01-01 00:00:00.004
2019-01-01 00:00:00.004
2019-01-01 00:00:01.006
2019-01-01 00:00:01.006
2019-01-01 00:00:01.005

输出

3

说明

样例 $3$ 中，前两个订单是同一秒内同一时刻（也是最早）下单，第三第四个订单不是当前秒内最早下单，不可免单，第五个订单可以免单。