UVa 145 Gondwanaland Telecom

题目描述

Gondwanaland Telecom \texttt{Gondwanaland Telecom}Gondwanaland Telecom公司根据通话距离和一天中的时间段对电话呼叫进行计费。计费依据如下费率表，其中计费步长与距离相关：

所有费率均为每分钟通话的费用（美元）。跨越不同费率时段的通话，将按照在各时段内实际通话时间分别计费。例如，一个通话从下午5 : 58 5:585:58开始，到下午6 : 04 6:046:04结束，将按2 22分钟白天费率和4 44分钟晚间费率计费。通话时间不足一分钟不记录，且任何通话不会超过24 2424小时。

编写一个程序，读取通话详情，计算相应费用。

输入格式

输入每行包含：计费步长（大写字母A到E）、被叫号码（7 77位数字和连字符组成的字符串，格式规范）、通话开始和结束时间，各部分之间恰好由一个空格分隔。时间以24 2424小时制的小时和分钟表示，小时和分钟之间用一个空格分隔，每个数字为两位。输入以单独一行包含一个#结束。

输出格式

输出包含：被叫号码、通话在各计费类别中的分钟数、计费步长和总费用，格式如下所示。

注意：下面示例输出的第一行并非实际输出内容，仅用于展示所需的制表格式。

示例输入：

A 183-5724 17 58 18 04 #

示例输出：

183-5724 2 4 0 A 0.44

题目分析与解题思路

本题的核心在于时间段的划分与累加计算。我们需要将一个通话的时长，按照三个不同的费率时段（白天、晚间、夜间）进行拆分，然后根据给定的距离费率步长（A AA到E EE）计算总费用。

关键点分析

1. 时间处理
   题目给出的时间是24 2424小时制，但通话可能跨越午夜（例如从23 : 50 23:5023:50到00 : 10 00:1000:10）。为了简化处理，我们可以将时间全部转换为从00 : 00 00:0000:00开始的分钟数。这样，通话的起始时间和结束时间就可以表示为一个整数（分钟数）。

2. 跨天通话
   如果结束时间小于开始时间，说明通话跨越了午夜，需要将结束时间加上1440 14401440分钟（一天的总分钟数）。此外，题目明确说明“通话不会超过24 2424小时”，且如果开始时间等于结束时间，则视为通话24 2424小时（即加上1440 14401440分钟）。

3. 费率时段划分
   一天中的费率时段如下：

   • 白天：08 : 00 − 18 : 00 08:00 - 18:0008:00−18:00（分钟数：480 480480-1079 10791079）
   • 晚间：18 : 00 − 22 : 00 18:00 - 22:0018:00−22:00（分钟数：1080 10801080-1319 13191319）
   • 夜间：22 : 00 − 08 : 00 22:00 - 08:0022:00−08:00（分钟数：1320 13201320-1439 14391439和0 00-479 479479）

   由于通话可能跨越午夜，我们需要考虑两天的时段。因此，我们可以将时段扩展为两个24 2424小时周期，即0 00到2880 28802880分钟。

4. 计算各时段通话分钟数
   我们需要计算在扩展后的时间段（从s t a r t M i n startMinstartMin到e n d M i n endMinendMin）内，落在每个费率时段的总分钟数。可以通过一个辅助函数getAnd来计算两个时间段的交集分钟数，并注意通话分钟数应减去1 11（因为通话的“分钟”是从开始时刻起算的整数分钟，例如从5 : 58 5:585:58到6 : 04 6:046:04，实际计费分钟为2 22和4 44，而非3 33和5 55）。

算法步骤

1. 读入一行数据，若为#则结束。
2. 将开始和结束时间转换为从00 : 00 00:0000:00开始的分钟数。
3. 处理跨天情况：
   • 若结束时间小于开始时间，或两者相等，则结束时间加上1440 14401440分钟。
4. 定义三个变量分别记录白天、晚间、夜间的总分钟数。
5. 通过getAnd函数计算在扩展后的时间段内，与各费率时段（考虑两个周期）的交集分钟数，并累加。
6. 根据距离步长（A − E A-EA−E）和对应的费率表计算总费用。
7. 按格式输出结果。

时间复杂度

每个通话的处理时间主要花费在getAnd函数的循环上，最坏情况下需要遍历2880 28802880分钟，因此时间复杂度为O ( 2880 ) = O ( 1 ) O(2880) = O(1)O(2880)=O(1)，对于题目给定的输入规模非常高效。

代码实现

// Gondwanaland Telecom// UVa ID: 145// Verdict: Accepted// Submission Date: 2016-01-22// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net//// In description: "Calls less than a minute are not recorded and no call// may last more than 24 hours. "// I miss the case of whole 24 hours! (start time == end time)#include<bits/stdc++.h>usingnamespacestd;intgetAnd(intstart1,intend1,intstart2,intend2){intminutes=0;for(inti=start1;i<=end1;i++)if(i>=start2&&i<=end2)minutes++;return(minutes>0?(minutes-1):0);}intmain(){string line,distance,number;intstartHour,startMin,endHour,endMin;doublecost[5][3]={{0.10,0.06,0.02},{0.25,0.15,0.05},{0.53,0.33,0.13},{0.87,0.47,0.17},{1.44,0.80,0.30}};while(getline(cin,line),line!="#"){istringstreamiss(line);iss>>distance>>number>>startHour>>startMin>>endHour>>endMin;startMin+=startHour*60;endMin+=endHour*60;if(endHour<startHour)endMin+=1440;elseif(endHour==startHour&&endMin<startMin)endMin+=1440;elseif(endHour==startHour&&endMin==startMin)endMin+=1440;doubletotalCost=0.0;intdayMin=0,eveningMin=0,nightMin=0;dayMin+=getAnd(startMin,endMin,480,1080);dayMin+=getAnd(startMin,endMin,1920,2520);eveningMin+=getAnd(startMin,endMin,1080,1320);eveningMin+=getAnd(startMin,endMin,2520,2760);nightMin+=getAnd(startMin,endMin,0,480);nightMin+=getAnd(startMin,endMin,1320,1920);nightMin+=getAnd(startMin,endMin,2760,2880);totalCost+=dayMin*cost[distance[0]-'A'][0];totalCost+=eveningMin*cost[distance[0]-'A'][1];totalCost+=nightMin*cost[distance[0]-'A'][2];cout<<setw(10)<<right<<number;cout<<setw(6)<<right<<dayMin;cout<<setw(6)<<right<<eveningMin;cout<<setw(6)<<right<<nightMin;cout<<setw(3)<<right<<distance;cout<<setw(8)<<right<<fixed<<setprecision(2)<<totalCost<<endl;}return0;}

总结

本题是一道典型的时间计算类模拟题，难点在于正确处理跨天通话和各费率时段的划分。通过将时间统一转换为分钟数，并扩展为两个周期来处理跨午夜的通话，可以大大简化计算逻辑。代码实现中需要注意边界条件，特别是开始时间等于结束时间的情况，应视为24 2424小时通话。