一、題目描述

云服務提供商會記錄客戶使用服務的計費日志。現在你需要根據這些日志為客戶計算話單總費用。

日志記錄包括：

• 時間戳（長度為 10 的字符串）
• 客戶標識（長度為 1~16 的字符串）
• 計費因子（長度為 1~16 的字符串）
• 計費時長（整數范圍為 0~100，超出視為非法并置為 0）

此外還提供一張計費因子單價表，未給出的因子視為單價為 0。

特殊規則：

• 同一客戶 同一時間戳 同一計費因子 的記錄只計一次，以首次記錄為準。

你需要輸出每個客戶的總話單費用，并按客戶標識的字典序升序輸出。

---

二、輸入描述

第一行：n 表示日志條數
接下來的 n 行：每行格式為 "時間戳,客戶標識,計費因子,計費時長"
下一行：m 表示計費因子單價數
接下來 m 行：每行格式為 "計費因子,單價"

---

三、輸出描述

每行一個客戶，格式為：

客戶名,總費用

按客戶標識升序輸出。

---

四、樣例輸入輸出

輸入示例：

5
1627845600,client1,factorA,10
1627845605,client2,factorB,15
1627845610,client1,factorA,5
1627845615,client1,factorB,8
1627845620,client2,factorB,20
2
factorA,5
factorB,7

輸出示例：

client1,131
client2,245

說明：

• client1:

  • factorA：10 + 5 = 15，單價 5 → 15×5=75
  • factorB：8，單價 7 → 8×7=56
  • 總計：75 + 56 = 131

• client2:

  • factorB：15 + 20 = 35，單價 7 → 35×7 = 245

---

五、解題思路分析

1. 去重處理：需要剔除重復記錄，即：客戶名 + 時間戳 + 計費因子 相同的記錄只取第一個。
2. 合法性檢查：時長必須在 [0, 100] 范圍，非法按 0 處理。
3. 單價匹配：若找不到對應的計費因子，則按 0 處理。
4. 客戶費用計算：統計每個客戶所有有效記錄對應的費用總和。
5. 排序輸出：按客戶名字典序升序輸出。

---

六、C實現源碼詳解（完整）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_N 1000            // 日志最大數量
#define MAX_M 1000            // 計費因子最大數量
#define MAX_LEN 100           // ID 字符串最大長度
#define MAX_CLIENTS 1000      // 客戶數量最大值
#define MAX_FACTORS 100       // 計費因子種類最大值// 客戶記錄結構體：包含客戶ID、計費因子ID、累計使用時長
typedef struct {char client_id[MAX_LEN];      // 客戶唯一標識char factor_id[MAX_LEN];      // 計費因子唯一標識int total_duration;           // 使用總時長
} ClientRecord;// 因子價格結構體：記錄每個因子的價格
typedef struct {char factor_id[MAX_LEN];      // 因子IDint price;                    // 因子的單價
} FactorPrice;ClientRecord records[MAX_CLIENTS * MAX_FACTORS]; // 所有客戶因子組合的記錄
int record_count = 0;                             // 當前記錄條數FactorPrice prices[MAX_FACTORS]; // 存儲所有計費因子的價格
int price_count = 0;             // 當前因子數量// 根據客戶ID和因子ID查找對應記錄在數組中的索引位置，若不存在返回 -1
int find_record_index(const char* client_id, const char* factor_id) {for (int i = 0; i < record_count; i++) {if (strcmp(records[i].client_id, client_id) == 0 &&strcmp(records[i].factor_id, factor_id) == 0) {return i; // 找到返回索引}}return -1; // 未找到
}// 獲取某個因子的單價，若找不到返回 0
int get_factor_price(const char* factor_id) {for (int i = 0; i < price_count; i++) {if (strcmp(prices[i].factor_id, factor_id) == 0) {return prices[i].price; // 返回對應單價}}return 0; // 未定義價格時按0處理
}int main() {int n;scanf("%d\n", &n); // 讀取日志記錄數（n 行）char line[200]; // 用于存儲一行輸入for (int i = 0; i < n; i++) {fgets(line, sizeof(line), stdin); // 讀取一行日志數據// 分割字符串，依次提取日志ID、客戶ID、因子ID、時長char* token = strtok(line, ",");char log_id[MAX_LEN], client_id[MAX_LEN], factor_id[MAX_LEN];int duration;strcpy(log_id, token); // 日志IDtoken = strtok(NULL, ",");strcpy(client_id, token); // 客戶IDtoken = strtok(NULL, ",");strcpy(factor_id, token); // 因子IDtoken = strtok(NULL, ",");duration = atoi(token); // 時長// 若時長不合法（負值或超過100），設為0if (duration < 0 || duration > 100) duration = 0;// 查找該客戶因子的記錄int idx = find_record_index(client_id, factor_id);if (idx != -1) {// 已有記錄，直接累計時長records[idx].total_duration += duration;} else {// 沒有記錄，新建一條strcpy(records[record_count].client_id, client_id);strcpy(records[record_count].factor_id, factor_id);records[record_count].total_duration = duration;record_count++; // 記錄數加一}}int m;scanf("%d\n", &m); // 讀取因子價格的條數for (int i = 0; i < m; i++) {fgets(line, sizeof(line), stdin); // 讀取一行因子信息char* token = strtok(line, ",");strcpy(prices[i].factor_id, token); // 因子IDtoken = strtok(NULL, ",");prices[i].price = atoi(token);      // 對應價格price_count++;}// 用于記錄已處理過的客戶，防止重復統計char processed_clients[MAX_CLIENTS][MAX_LEN];int processed_count = 0;for (int i = 0; i < record_count; i++) {int already_processed = 0;// 判斷該客戶是否已經處理過for (int j = 0; j < processed_count; j++) {if (strcmp(processed_clients[j], records[i].client_id) == 0) {already_processed = 1;break;}}if (already_processed) continue; // 已處理，跳過// 標記為已處理strcpy(processed_clients[processed_count++], records[i].client_id);int total_cost = 0; // 該客戶總費用// 累計該客戶所有因子的費用for (int j = 0; j < record_count; j++) {if (strcmp(records[j].client_id, records[i].client_id) == 0) {int price = get_factor_price(records[j].factor_id);total_cost += records[j].total_duration * price;}}// 輸出客戶ID與其總費用printf("%s,%d\n", records[i].client_id, total_cost);}return 0; // 程序結束
}

---

七、復雜度分析

• 時間復雜度：
  • 去重處理 + 數據讀取：$O(n)$
  • 因子價格映射：$O(m)$
  • 費用計算：$O(n)$
  • 排序輸出：$O(k\log k)$（k 為客戶數）
• 空間復雜度：$O(n+m)$

---