刷题笔记合集🔗

免单统计

问题描述

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

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

输入格式

第一行为一个整数 ，表示顾客人数。

接下来 行数据，每一行表示一位顾客的下单时间，以（年-月-日时-分-秒.毫秒） yyyy-MM-ddHH:mm:ss.fff 形式给出。

其中：

所有输入保证合法。

输出格式

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

样例输入

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

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

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

样例输出

1

3

3

数据范围

题解

这道题要求我们确定哪些订单可以享受免单优惠—即在每一秒内最早下单的顾客（可能有多人同时下单）。

解题思路如下：

首先要按照时间戳对所有订单进行排序，然后按照秒级别进行分组，找出每组中时间戳最小的订单。这些订单对应的顾客就是可以享受免单的人。

具体来说，我们可以按照以下步骤来解决：

1. 将所有订单时间按照时间戳大小排序
2. 遍历排序后的订单，记录每一秒内出现的最早订单时间
3. 将相同秒内相同时间戳（最早）的订单都标记为可免单
4. 统计可免单的订单数量

在实现上，可以采用两种方法：

1. 用栈来保存所有可免单的订单
2. 用标记数组记录每个订单是否可免单

时间复杂度分析：

• 排序时间为O(n log n)，这是算法的主要时间消耗
• 遍历订单时间为O(n)
• 总时间复杂度为O(n log n)

空间复杂度为O(n)，需要保存所有订单及其状态。

这个算法在n最大为50000的情况下表现良好，排序操作耗时可接受。如果输入数据已经按时间排序，算法可以进一步优化。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取订单数量
n = int(input())

# 读取所有订单时间
orders = []
for i in range(n):
    orders.append(input())

# 对订单按时间排序
orders.sort()

# 用栈保存可免单的订单
free_orders = []
i = 0

while i < n:
    # 当前订单
    order = orders[i]
    
    # 提取订单秒级别信息（去掉毫秒部分）
    second_part = order[:19]
    
    # 当前订单毫秒值
    min_time = order
    
    # 对比同一秒内的所有订单，找最早时刻
    j = i
    while j < n and orders[j][:19] == second_part:
        if orders[j] < min_time:
            min_time = orders[j]
        j += 1
    
    # 将同一秒内最早时刻的订单标记为免单
    for k in range(i, j):
        if orders[k] == min_time:
            free_orders.append(orders[k])
    
    # 移动到下一秒
    i = j

# 输出免单数量
print(len(free_orders))

• Cpp