核心内容摘要
全球首款896线四激光量产SUV，岚图泰山Ultra/黑武士17日上市
题目描述Gondwanaland Telecom \texttt{Gondwanaland Telecom}Gondwanaland Telecom公司根据通话距离和一天中的时间段对电话呼叫进行计费。
计费依据如下费率表其中计费步长与距离相关计费步长距离白天费率8 : 00 − 18 : 00 8:
:008:00−18:00晚间费率18 : 00 − 22 : 00 18:
:0018:00−22:00夜间费率22 : 00 − 8 : 00 22:
:0022:00−8:00A AA
10
0.
100.
1
06
0.
060.
0
02
0.
0
02B BB
25
0.
250.
2
15
0.
150.
1
05
0.
0
05C CC
53
0.
530.
5
33
0.
330.
3
13
0.
1
13D DD
87
0.
870.
8
47
0.
470.
4
17
0.
1
17E EE
44
1.
441.
4
80
0.
800.
8
30
0.
3
30所有费率均为每分钟通话的费用美元。
跨越不同费率时段的通话将按照在各时段内实际通话时间分别计费。
例如一个通话从下午5 : 58 5:585:58开始到下午6 : 04 6:046:04结束将按2 22分钟白天费率和4 44分钟晚间费率计费。
通话时间不足一分钟不记录且任何通话不会超过24 2424小时。
编写一个程序读取通话详情计算相应费用。
输入格式输入每行包含计费步长大写字母A到E、被叫号码7 77位数字和连字符组成的字符串格式规范、通话开始和结束时间各部分之间恰好由一个空格分隔。
时间以24 2424小时制的小时和分钟表示小时和分钟之间用一个空格分隔每个数字为两位。
输入以单独一行包含一个#结束。
输出格式输出包含被叫号码、通话在各计费类别中的分钟数、计费步长和总费用格式如下所示。
注意下面示例输出的第一行并非实际输出内容仅用于展示所需的制表格式。
示例输入A
17 58 18 04 #示例输出
2 4 0 A
44题目分析与解题思路本题的核心在于时间段的划分与累加计算。
我们需要将一个通话的时长按照三个不同的费率时段白天、晚间、夜间进行拆分然后根据给定的距离费率步长A AA到E EE计算总费用。
关键点分析时间处理题目给出的时间是24 2424小时制但通话可能跨越午夜例如从23 : 50 23:5023:50到00 : 10 00:1000:10。
为了简化处理我们可以将时间全部转换为从00 : 00 00:0000:00开始的分钟数。
这样通话的起始时间和结束时间就可以表示为一个整数分钟数。
跨天通话如果结束时间小于开始时间说明通话跨越了午夜需要将结束时间加上1440 14401440分钟一天的总分钟数。
此外题目明确说明“通话不会超过24 2424小时”且如果开始时间等于结束时间则视为通话24 2424小时即加上1440 14401440分钟。
费率时段划分一天中的费率时段如下白天08 : 00 − 18 : 00 08:00 - 18:0008:00−18:00分钟数480
10791079晚间18 : 00 − 22 : 00 18:00 - 22:0018:00−22:00分钟数1080
13191319夜间22 : 00 − 08 : 00 22:00 - 08:0022:00−08:00分钟数1320
14391439和0
479479由于通话可能跨越午夜我们需要考虑两天的时段。
因此我们可以将时段扩展为两个24 2424小时周期即0 00到2880 28802880分钟。
计算各时段通话分钟数我们需要计算在扩展后的时间段从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。
算法步骤读入一行数据若为#则结束。
将开始和结束时间转换为从00 : 00 00:0000:00开始的分钟数。
处理跨天情况若结束时间小于开始时间或两者相等则结束时间加上1440 14401440分钟。
定义三个变量分别记录白天、晚间、夜间的总分钟数。
通过getAnd函数计算在扩展后的时间段内与各费率时段考虑两个周期的交集分钟数并累加。
根据距离步长A − E A-EA−E和对应的费率表计算总费用。
按格式输出结果。
时间复杂度每个通话的处理时间主要花费在getAnd函数的循环上最坏情况下需要遍历2880 28802880分钟因此时间复杂度为O ( 2880 ) O ( 1 ) O(
O(
O(
O(
对于题目给定的输入规模非常高效。
代码实现// Gondwanaland Telecom// UVa ID: 145// Verdict: Accepted// Submission Date:
// UVa Run Time:
000s//// 版权所有C2016邱秋。
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)#includebits/stdc.husingnamespacestd;intgetAnd(intstart1,intend1,intstart2,intend
{intminutes0;for(intistart1;iend1;i)if(istart2iend
minutes;return(minutes0?(minutes-
:
;}intmain(){string line,distance,number;intstartHour,startMin,endHour,endMin;doublecost[5][3];while(getline(cin,line),line!#){istringstreamiss(line);issdistancenumberstartHourstartMinendHourendMin;startMinstartHour*60;endMinendHour*60;if(endHourstartHour)endMin1440;elseif(endHourstartHourendMinstartMin)endMin1440;elseif(endHourstartHourendMinstartMin)endMin1440;doubletotalCost
0;intdayMin0,eveningMin0,nightMin0;dayMingetAnd(startMin,endMin,480,
;dayMingetAnd(startMin,endMin,1920,
;eveningMingetAnd(startMin,endMin,1080,
;eveningMingetAnd(startMin,endMin,2520,
;nightMingetAnd(startMin,endMin,0,
;nightMingetAnd(startMin,endMin,1320,
;nightMingetAnd(startMin,endMin,2760,
;totalCostdayMin*cost[distance[0]-A][0];totalCosteveningMin*cost[distance[0]-A][1];totalCostnightMin*cost[distance[0]-A][2];coutsetw(
rightnumber;coutsetw(
rightdayMin;coutsetw(
righteveningMin;coutsetw(
rightnightMin;coutsetw(
rightdistance;coutsetw(
rightfixedsetprecision(
totalCostendl;}return0;}
总结本题是一道典型的时间计算类模拟题难点在于正确处理跨天通话和各费率时段的划分。
通过将时间统一转换为分钟数并扩展为两个周期来处理跨午夜的通话可以大大简化计算逻辑。
代码实现中需要注意边界条件特别是开始时间等于结束时间的情况应视为24 2424小时通话。