刷题笔记合集🔗

优选核酸检测点

问题描述

小柯要去外地出差，需要做核酸，需要在指定时间点前做完核酸，请帮她找到满足条件的核酸检测点。

• 给出一组核酸检测点的距离和每个核酸检测点当前的人数
• 给出小柯要去做核酸的出发时间，出发时间是 分钟的倍数，同时给出小柯做核酸的最晚结束时间
• 题目中给出的距离是整数，单位是公里，时间 分钟为一基本单位

去找核酸点时，有如下的限制：

• 去往核酸点的路上，每公里距离花费时间 分钟，费用是 元
• 核酸点每检测一个人的时间花费是 分钟
• 每个核酸点工作时间都是 点到 点中间不休息，核酸点准时工作，早到晚到都不检测
• 核酸检测结果可立刻知道
• 在小柯去某个核酸点的路上花费的时间内，此核酸检测点的人数是动态变化的，变化规则是：

1. 在非核酸检测时间内，没有人排队
2. 点- 点每分钟增加 人
3. 点- 点每分钟增加 人
4. 点- 点每分钟增加 人
5. 其他时间每 分钟增加 人

要求将所有满足条件的核酸检测点按照优选规则排序列出：

优选规则：

1. 花费时间最少的核酸检测点排在前面
2. 花费时间一样，花费费用最少的核酸检测点排在前面
3. 时间和费用一样，则ID值最小的排在前面

输入格式

第一行输入两个整数 和 ，表示当前时间的小时数和分钟数。

第二行输入两个整数 和 ，表示指定完成核酸时间的小时数和分钟数。

第三行输入一个整数 ，表示所有核酸检测点个数。

接下来 行，每行输入三个整数 、 和 ，分别表示核酸点的ID值、核酸检测点距离小柯的距离和核酸检测点当前检测的人数。

输出格式

第一行输出一个整数 ，表示满足要求的核酸检测点个数。

接下来 行，每行输出三个整数 、 和 ，分别表示选择后的核酸检测点ID、做完核酸花费的总时间（分钟）和去该核酸点花费的费用。

样例输入

10 30
14 50
3
1 10 19
2 8 20
3 21 3

样例输出

2
2 80 80
1 190 100

数据范围

题解

这道题需要我们根据给定的规则来计算去各个核酸检测点所需的总时间和费用，然后按照题目要求进行筛选和排序。

解题思路如下：

1. 计算到达各检测点的时间：

   • 出发时间 + 路程时间 = 到达时间
   • 如果到达时间早于8点，则实际到达时间调整为8点

2. 计算到达时人数的变化：

   • 需要考虑在小柯从出发到到达期间，核酸检测点人数的动态变化
   • 按照题目给出的时间段规则，计算在不同时间段内人数的增减变化
   • 考虑时间段的交集，统计总的人数变化

3. 计算总花费时间：

   • 路程时间 + 等待时间 = 总花费时间
   • 等待时间 = 到达时的排队人数

4. 筛选和排序：

   • 筛选出在限定时间内可以完成的检测点
   • 按照总花费时间、费用和ID进行排序

关键点在于如何处理时间段交集。我们需要计算出小柯从出发到到达的时间段，与各个特殊时间段（如8点-10点、12点-14点等）的交集时长，然后根据相应的人数变化规则计算人数变化。

时间复杂度分析：假设核酸检测点的数量为N，则时间复杂度为O(N log N)，主要来自于对筛选后的检测点进行排序。空间复杂度为O(N)，用于存储检测点信息。对于题目给定的约束（N最大为100），这个算法是非常高效的。

参考代码

• Python

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

# 读取输入
h1, m1 = map(int, input().split())
h2, m2 = map(int, input().split())
n = int(input())
sites = []
for _ in range(n):
    id, dist, people = map(int, input().split())
    sites.append((id, dist, people))

def calculate_intersection(start1, end1, start2, end2):
    """计算两个时间段的交集长度"""
    if start1 <= start2 < end1:
        return min(end1, end2) - start2
    
    if start2 <= start1 < end2:
        return min(end1, end2) - start1
    
    return 0

def find_best_sites(h1, m1, h2, m2, sites):
    start_time = h1 * 60 + m1  # 出发时间（分钟）
    latest_end_time = min(h2 * 60 + m2, 20 * 60)  # 最晚完成时间（不能超过20点）
    
    # 定义各时间段内人数的变化率
    time_changes = [
        [8 * 60, 10 * 60, 2],       # 8点-10点，每分钟净增2人
        [10 * 60, 12 * 60, -0.8],   # 10点-12点，每分钟净减0.8人
        [12 * 60, 14 * 60, 9],      # 12点-14点，每分钟净增9人
        [14 * 60, 18 * 60, -0.8],   # 14点-18点，每分钟净减0.8人
        [18 * 60, 20 * 60, 19]      # 18点-20点，每分钟净增19人
    ]
    
    results = []
    for site_id, distance, initial_people in sites:
        travel_time = distance * 10  # 路程时间（分钟）
        travel_cost = distance * 10  # 路程费用（元）
        
        arrive_time = start_time + travel_time  # 到达时间
        
        # 如果早于8点到达，则调整为8点
        if arrive_time < 8 * 60:
            arrive_time = 8 * 60
            total_time = arrive_time - start_time + initial_people
            results.append((site_id, total_time, travel_cost))
            continue
        
        # 计算到达时的排队人数变化
        people_count = initial_people
        for segment_start, segment_end, change_rate in time_changes:
            overlap = calculate_intersection(start_time, arrive_time, segment_start, segment_end)
            if overlap > 0:
                people_count += overlap * change_rate
                people_count = max(0, people_count)  # 人数不能为负
        
        # 计算总时间 = 路程时间 + 等待时间
        total_time = arrive_time - start_time + people_count
        
        # 检查是否在限定时间内可以完成
        if start_time + total_time <= latest_end_time:
            results.append((site_id, int(total_time), travel_cost))
    
    # 按要求排序：花费时间少的优先，时间相同则费用少的优先，都相同则ID小的优先
    results.sort(key=lambda x: (x[1], x[2], x[0]))
    
    return results

# 计算并输出结果
result = find_best_sites(h1, m1, h2, m2, sites)
print(len(result))
for site_id, time, cost in result:
    print(f"{site_id} {time} {cost}")

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 计算两个时间段的交集长度
double intersection(