题目
长途电话公司按以下规则向客户收费：
拨打长途电话每分钟要花费一定的费用，具体收费取决于拨打电话的时间。
客户开始拨打长途电话的时间将被记录，客户挂断电话的时间也将被记录。
每个月都要给客户发送一次话费账单，账单中应包含每次通话记录以及相关收费等信息。
给定一组电话记录，你的工作是为客户准备帐单。
输入格式
输入包含两部分：费率结构和电话记录。
费率结构由一行组成，该行包含24个非负整数，分别表示从 00:00-01:00 的收费（分/分钟），从 01:00-02:00 的收费，以此类推…
下一行包含一个正整数 N。
接下来 N 行，每行包含一条记录。
每个记录由客户名称（最多 20 个字符的字符串，不带空格），时间和日期（mm:dd:hh:mm）以及单词 on-line 或 off-line 组成。
所有日期都在同一个月内，每个 on-line 记录都与按时间顺序排列的同一位客户的下一条记录配对，但前提是这条记录是 off-line。
所有未与 off-line 记录配对的 on-line 记录以及未与 on-line 记录配对的 off-line 记录都必须忽略。
输入中至少包含一个成功的配对。
同一客户在同一时间不会有两个或以上的电话记录。
使用 24 小时制记录时间。
输出格式
你需要为每个客户打印电话费。
账单必须按照客户姓名的字母顺序（按ASCII码顺序，大写字母在前，小写字母在后）打印。
对于每个客户，首先以示例显示的格式在一行中打印客户名称和帐单月份。
然后，对于每个通话时间段，在一行中分别打印开始和结束时间和日期（dd:hh:mm），持续时间（以分钟为单位）和通话费用。
通话必须按时间顺序列出。
最后，以示例显示的格式打印该月的总费用。
注意，没有任何有效通话记录的客户直接忽略，不予打印账单。
数据范围
1≤N≤1000
输入样例：
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
输出样例：
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

解法：模拟

计算花费可以用前缀和
时间复杂度O(nlogn)，空间复杂度O(n)

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <map>
  6. #include <vector>
  8. using namespace std;
  10. const int N = 1010, M = 31 * 1440 + 10;
  12. int n;
  13. int cost[24];  // 每个时间段的话费
  14. double sum[M];  // 从当月1号00:00开始到每个时刻所花费的钱数
  16. struct Record
  17. {
  18.     int minutes;
  19.     string state;
  20.     string format_time;
  22.     bool operator< (const Record& t) const
  23.     {
  24.         return minutes < t.minutes;
  25.     }
  26. };
  28. map<string, vector<Record>> persons;  // string自动按字典序排
  30. int main()
  31. {
  32.     for (int i = 0; i < 24; i ++ ) cin >> cost[i];
  33.     // 09：59~10：00按09的费用算
  34.     for (int i = 1; i < M; i ++ ) sum[i] = sum[i - 1] + cost[(i - 1) % 1440 / 60] / 100.0;
  36.     cin >> n;
  37.     char name[25], state[10], format_time[20];
  38.     int month, day, hour, minute;
  39.     for (int i = 0; i < n; i ++ )
  40.     {
  41.         scanf("%s %d:%d:%d:%d %s", name, &month, &day, &hour, &minute, state);
  42.         sprintf(format_time, "%02d:%02d:%02d", day, hour, minute);
  44.         int minutes = (day - 1) * 1440 + hour * 60 + minute;
  45.         persons[name].push_back({minutes, state, format_time});
  46.     }
  48.     for (auto &person : persons)
  49.     {
  50.         auto name = person.first;
  51.         auto records = person.second;
  52.         sort(records.begin(), records.end());
  54.         double total = 0;
  55.         for (int i = 0; i + 1 < records.size(); i ++ )
  56.         {
  57.             auto a = records[i], b = records[i + 1];
  58.             if (a.state == "on-line" && b.state == "off-line")
  59.             {
  60.                 if (!total) printf("%s %02d\n", name.c_str(), month);  // C语言中必须将string转换成char*
  61.                 cout << a.format_time << ' ' << b.format_time;
  63.                 double c = sum[b.minutes] - sum[a.minutes];
  64.                 printf(" %d $%.2lf\n", b.minutes - a.minutes, c);
  65.                 total += c;
  66.             }
  67.         }
  69.         if (total) printf("Total amount: $%.2lf\n", total);
  70.     }
  72.     return 0;
  73. }