首页 > ACM题库 > UVA > UVa-145-Gondwanaland Telecom-[模拟]
2014
01-22

UVa-145-Gondwanaland Telecom-[模拟]

Time limit: 3.000 seconds
限时:3.000秒

 

Problem
问题

Gondwanaland Telecom makes charges for calls according to distance and time of day. The basis of the charging is contained in the following schedule, where the charging step is related to the distance:
冈瓦纳电信公司按照一天中的时段和通话距离来收取话费。下表列出了基本通话费方案,其中话费阶段是按距离远近安排的。

 

Charging Step
(distance)
Day Rate
8am to 6pm
Evening Rate
6pm to 10pm
Night Rate
10pm to 8am
A 0.10 0.06 0.02
B 0.25 0.15 0.05
C 0.53 0.33 0.13
D 0.87 0.47 0.17
E 1.44 0.80 0.30

 

All charges are in dollars per minute of the call. Calls which straddle a rate boundary are charged according to the time spent in each section. Thus a call starting at 5:58 pm and terminating at 6:04 pm will be charged for 2 minutes at the day rate and for 4 minutes at the evening rate. Calls less than a minute are not recorded and no call may last more than 24 hours.
所有话费都是按照通话的分钟数累计的。若一次通话跨越了两个时段,则分别按照在各时段内的通话时间和费率进行收费。比如一次通话由晚5:58开始到晚6:04结束,则按2分钟的白天通话和4分钟的夜晚通话费率计算。通话少于1分钟的不计费,最长的通话不会超过24小时。

Write a program that reads call details and calculates the corresponding charges.
写一个程序读取所有的通话信息并计算对应的话费。

 

Input and Output
输入与输出

Input lines will consist of the charging step (upper case letter ‘A’..’E'), the number called (a string of 7 digits and a hyphen in the approved format) and the start and end times of the call, all separated by exactly one blank. Times are recorded as hours and minutes in the 24 hour clock, separated by one blank and with two digits for each number. Input will be terminated by a line consisting of a single #.
输入由多行组成,每一行数据都包括:话费阶段(大写字母“A”到“E”),拨出的号码(一个7位数组和横线组成的字符串),通话的开始和结束时间。这些数据间都由空格隔开。时间均由24小时制的小时和分钟表示,之间由一个空格隔开,每个数字都有两位数(译注:不足两位的前面补零)。只有一个#号的单独一行表示输入结束。

Output will consist of the called number, the time in minutes the call spent in each of the charge categories, the charging step and the total cost in the format shown below.
输出的每一行要包括拨出的号码,每一个话费阶段的分钟数,话费阶段编号以及总费用。并按如下格式输出。

 

Sample Input
输入示例

A 183-5724 17 58 18 04
#

 

Sample Output
输出示例

0         10        20        30
123456789012345678901234567890123456789

  183-5724     2     4     0  A    0.44

译注:原文中的示例输出为一张很不清晰的图片。上面的数据来自我AC的程序输出,格式与原图完全相同。最上面灰色的两行为表头表示字符的位置,只作示例参照,你的程序不要输出该表头。红色的数字表示下面一列数据需要对齐的位置(在下面一列的左侧为左对齐,在右侧为右对齐)。

 

Analysis
输出示例

一道没有任何难度的题目,解法也非常多,主要是练习格式化的输出。只需要注意两点,一是跨过24点(0点)的话时要能够正确计算,二是按题目要求话时可以等于24小时,即开始和结束时间相同。C++的格式化数据方法详参下面的代码。

 

Solution
解答

#include <iomanip>
#include <iostream>
#include <string>
using namespace std;
//按照指定的开始和起始时间统计各时间段内的分钟数
void StepStatic(int nBeg, int nEnd, int *pCate, int nCnt, int *pResult) {
	int ic= 0; //ic表示当前时段,下面的循环找到开始时间所在时段
	for (; ic < nCnt - 1 && nBeg >= pCate[ic]; ++ic);
	//开始时间的时段减去开始前的无通话时间
	pResult[ic - 1] -= (nBeg - pCate[ic - 1]);
	//循环统计每个时段的时间
	for (--ic; ic < nCnt - 1 && nEnd >= pCate[ic]; ++ic) {
		pResult[ic] += pCate[ic + 1] - pCate[ic];
	}
	//结束时间所在时段减去结束后的无通话时间
	pResult[ic - 1] -= (pCate[ic] - nEnd);
}
int main(void) {
	int Cate[] = {0, 8 * 60, 18 * 60, 22 * 60, 24 * 60}; //时间段分钟数
	const int nCnt = sizeof(Cate) / sizeof(Cate[0]); //时间段数
	int Rate[5][3] = { {10, 6, 2}, {25, 15, 5}, {53, 33, 13},
		{87, 47, 17}, {144, 80, 30} }; //费率表
	cout.setf(ios_base::right); //输出格式居右对齐
	//循环处理每一行输入的数据,直到出现#号为止
	for (char cStep; cin >> cStep && cStep != '#'; cout << endl) {
		string Num;
		int BegH, BegM, EndH, EndM, nCharge = 0, Result[nCnt - 1] = {0};
		cin >> Num >> BegH >> BegM >> EndH >> EndM; //读入数据
		int nBeg = BegH * 60 + BegM, nEnd = EndH * 60 + EndM;
		if (nEnd <= nBeg) { //如果开始时间小于或等于结束时间
			//先统计从开始时间到24点,再从0点到结束时间
			StepStatic(nBeg, Cate[nCnt - 1], Cate, nCnt, Result);
			StepStatic(0, nEnd, Cate, nCnt, Result);
		}
		else { //否则直接统计从开始时间到结束时间
			StepStatic(nBeg, nEnd, Cate, nCnt, Result);
		}
		//将最后到24点的时段和从0点开始的时段合并
		Result[nCnt - 2] += Result[0];
		cout << setw(10) << Num; //输出电话号码
		for (int i = 1; i < nCnt - 1; ++i) { //统计话费并输出各时段话时
			nCharge += Rate[cStep - 'A'][i - 1] * Result[i];
			cout << setw(6) << Result[i];
		}
		cout << setw(3) << cStep; //输出距离及总话费
		cout << setw(8) << fixed << setprecision(2) << (nCharge / 100.0f);
	}
	return 0;
}

转自:http://www.cnblogs.com/devymex/archive/2010/09/06/1818058.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮