PAT A1016:Phone Bills

非常复杂的模拟实现题,涉及到排序、时间日期处理等问题

题目内容

A long-distance telephone company charges its customers by the following rules:

Making a long-distance call costs a certain amount per minute, depending on the time of day when the call is made. When a customer starts connecting a long-distance call, the time will be recorded, and so will be the time when the customer hangs up the phone. Every calendar month, a bill is sent to the customer for each minute called (at a rate determined by the time of day). Your job is to prepare the bills for each month, given a set of phone call records.

Input Specification:

Each input file contains one test case. Each case has two parts: the rate structure, and the phone call records.

The rate structure consists of a line with 24 non-negative integers denoting the toll (cents/minute) from 00:00 - 01:00, the toll from 01:00 - 02:00, and so on for each hour in the day.

The next line contains a positive number $N (\leqslant 1000)$, followed by $N$ lines of records. Each phone call record consists of the name of the customer (string of up to 20 characters without space), the time and date (MM:dd:HH:mm), and the word on-line or off-line.

For each test case, all dates will be within a single month. Each on-line record is paired with the chronologically next record for the same customer provided it is an off-line record. Any on-line records that are not paired with an off-line record are ignored, as are off-line records not paired with an on-line record. It is guaranteed that at least one call is well paired in the input. You may assume that no two records for the same customer have the same time. Times are recorded using a 24-hour clock.

Output Specification:

For each test case, you must print a phone bill for each customer.

Bills must be printed in alphabetical order of customers’ names. For each customer, first print in a line the name of the customer and the month of the bill in the format shown by the sample. Then for each time period of a call, print in one line the beginning and ending time and date (dd:HH:mm), the lasting time (in minute) and the charge of the call. The calls must be listed in chronological order. Finally, print the total charge for the month in the format shown by the sample.

Sample Input:

10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
10
CYLL 01:01:06:01 on-line
CYLL 01:28:16:05 off-line
CYJJ 01:01:07:00 off-line
CYLL 01:01:08:03 off-line
CYJJ 01:01:05:59 on-line
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:04:23:59 off-line

Sample Output:

CYJJ 01
01:05:59 01:07:00 61 $12.10
Total amount: $12.10
CYLL 01
01:06:01 01:08:03 122 $24.40
28:15:41 28:16:05 24 $3.85
Total amount: $28.25
aaa 01
02:00:01 04:23:59 4318 $638.80
Total amount: $638.80

题目要点

本题 25 分,题干内容多,各种细节繁复,所以在做题时要认真审题,将整个问题分成若干个模块分别解决。除了输入和输出外,主要是三方面:①数据排序 ②筛选出可以“拨打-挂断”配对的数据 ③计算各个配对的费用,再对各个用户总费用求和。

首先需要对数据进行排序。将用户按字典序排列,每个用户的通话记录再按照时间升序排列。由于输入的时间格式比较严谨,因此直接对字符串排序也是可以的。Python需要先对映射为键名的用户排序,然后遍历各个键值,将键值中存的多条通话记录按时间排序。

很容易想到,寻找“拨打-挂断”配对数据的方法是先将数据按时间递增顺序排列,然后利用循环,判断当前状态是是否是“拨打”且下一个状态是否为“挂断”,如果满足,那么这两条数据是配对的,如果不满足,继续查找。

使用while语句处理起来更加方便,当找到配对的数据时,由于数据是两两配对互不重复,因此i指针可以递增2,这样免去不必要的比较,可以提高效率。

i = 0
while i < len(record)-1:
    if record[i].status == 'on-line' and record[i+1].status == 'off-line':
        print(record[i].data, record[i+1].data) # 输出配对数据
        i += 2
    else:
    	i += 1

计算电话费用比较麻烦,因为还要考虑不同时段的单价,这里给出一种比较好理解的算法。首先建立小时对应单价(美元/分钟)长度为24的列表。然后将拨号时间start和挂断时间end拆分成完整小时不足小时(分钟)两类数据。

  • 完整小时是从startend取整小时的左闭右开区间,比如02:00:0104:23:59,我们只取小时数,分别为$24\times 2 + 0=48$到$24\times 4 + 23=119$,取48~119(不含119)之间的数,分别求24的余数,得到的即为每天对应的小时,再以此为下标取单价列表,对所有值求和,得到完整小时的总金额。在Python中列表推导式可以很容易实现这一过程。

    price = [10,10,10,10,10,10,20,20,20,15,15,15,15,15,15,15,20,30,20,15,15,10,10,10]
    hour_amount = sum( [ price[i%24]*60 for i in range(48, 119) ] )
    
  • 不足小时是指剔除完整的小时后剩余的若干分钟。比如挂断时间04:23:59只取小时数是$24\times 4 + 23=119$,那么还剩余59分钟不足一小时,需要单独累计。对于拨号时间02:00:01,取小时数时实际上是看作一个完整的小时,因此过去的这1分钟要扣除,因此要乘以负一。如下所示

    start.hour, end.hour = 48, 119
    start.minute, end.minute = 1, 59
    minute_amount = -1*price[start.hour%24]*start.minute + price[end.hour%24]*end.minute
    

各个测试点考察的点如下:

测试点0:简单,没有坑

测试点1:没有成功拨打电话的用户不予输出,参考额外样例1

测试点2:电话拨打挂断在不同天的同一个小时,参考额外样例2

测试点3:电话拨打挂断在同一天的同一个小时,参考额外样例2

额外样例1

// 输入
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
5
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:02:00:02 off-line
// 结果
aaa 01
02:00:01 02:00:02 1 $0.10
Total amount: $0.10

额外样例2

// 输入
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
10
CYLL 01:01:06:01 on-line
CYLL 01:28:16:05 off-line
CYJJ 01:01:05:59 on-line
CYJJ 01:01:07:00 off-line
CYLL 01:01:08:03 off-line
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:04:23:59 off-line
// 结果
CYLL 01
01:06:01 01:07:00 59 $11.80
01:08:03 01:08:09 6 $1.20
01:08:09 02:00:01 952 $151.30
29:02:24 30:23:59 2735 $411.50
Total amount: $575.80
MQ 01
03:04:05 03:04:06 1 $0.10
Total amount: $0.10

AC 源代码

def fee(start, end):
    period = '{} {}'.format(start.split(':',1)[1], end.split(':',1)[1])
    start = list(map(int, start.split(':')))
    end = list(map(int, end.split(':')))
    part = -start[-1] + end[-1]
    start_h = start[1] * 24 + start[2]
    end_h = end[1] * 24 + end[2]
    minute = (end_h - start_h)*60 + part
    part_fee = -start[-1] * price[start[-2]] + end[-1] * price[end[-2]]
    amount = sum([price[hour % 24] * 60 for hour in range(start_h, end_h)])
    amount = (amount + part_fee) / 100
    print('{} {} ${:.2f}'.format(period, minute, amount))
    return amount

record = {}

price = list(map(int, input().split()))
count = int(input())
for _ in range(count):
    name, date, state = input().split()
    if name not in record:
        record[name] = []
    record[name].append([date, state])

record = sorted(record.items(), key=lambda x: x[0])

for name, rec in record:
    i, amount = 0, 0.0
    rec.sort(key=lambda x:x[0])
    month = rec[0][0].split(':')[0]
    has_record = False
    while i < len(rec)-1:
        if rec[i][1] == 'on-line' and rec[i+1][1] == 'off-line':
            if not has_record:
                print(name, month)
            has_record = True
            dail_amount = fee(rec[i][0], rec[i+1][0])
            amount += dail_amount
            i += 2
            continue
        i += 1
    if has_record:
        print('Total amount: ${:.2f}'.format(amount))

参考来源

https://blog.csdn.net/lannister_awalys_pay/article/details/86693947

柳神的另类思路:https://www.liuchuo.net/archives/2350

模块化的C++代码:https://segmentfault.com/a/1190000024570906

思路清晰的C代码:https://www.cnblogs.com/caiyishuai/p/11296926.html