华为校招机试 - 云服务计费（20240410）

╰半夏微凉° 2024-04-21 08:26 71阅读 0赞

#### 在线OJ测试 ####

[题目详情 - 云服务计费 - HydroOJ][- _ - HydroOJ]

#### 题目描述 ####

编写一个程序为某云服务计算客户话单，输入为某云服务的计费日志和各种计费因子的计费单价的列表，计费日志内容包含 4 个字段：

*  时间戳
 *  客户标识
 *  计费因子
 *  计费时长

日志中如果同一客户、同一计费因子、在相同时间戳上报多次话单只能计费一次，选先上报的日志计费。

计算每个客户的话单总费用。

#### 输入描述 ####

第 1 行表示**计费日志的条数** n

*  n 是一个正整数，范围是：1 ≤ n ≤ 1000

第 2 到 n+1 行表示**云服务的计费日志**，共 4 列：

*  第 1 列表示**时间戳**（是一个数字字符串，长度为10）
 *  第 2 列表示**客户标识**（是一个字符串，长度为1-16）
 *  第 3 列表示**计费因子**（是一个字符串，长度为1-16，计费因子查不到时认为计费因子单价是0）
 *  第 4 列表示**计费时长**（范围为0-100，当计费时长不在范围内要认为是计费日志有问题，当成计费为 0 处理)
 *  这4个字段使用逗号分隔

第 n+2 行表示**计费因子的数量** m

*  m 是一个正整数，范围是：1 ≤ m ≤ 100

第 n+3 到 n+3+m 行表示**各种计费因子的计费单价的列表**，该表有 2 列：

*  第1列表示**计费因子** (是一个字符串，长度为1-16)
 *  第2列表示**单价**(是一个正整数，范围为1~100)
 *  这2个字段使用逗号分隔

#### 输出描述 ####

每个客户的话单总费用，共 2 列：

*  第 1 列表示客户名
 *  第 2 列表示话单费用

2列用逗号分割，输出按客户标识字典序升序排序。

#### 用例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">5<br> 1627845600,client1,factorA,10<br> 1627845605,client2,factorB,15<br> 1627845610,client1,factorA,5<br> 1627845610,client1,factorB,8<br> 1627845620,client2,factorB,20<br> 2<br> factorA,5<br> factorB,7</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">client1,131<br> client2,245</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;">client1 =&nbsp;15 × 5 + 8 × 7 = 131<br> client2 =&nbsp;0 × 5 + 35 × 7 = 245</td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

本题是一道逻辑模拟题。

主要难点在于细节把握，有如下细节

1.  日志中如果同一客户、同一计费因子、在相同时间戳上报多次话单只能计费一次，选先上报的日志计费。
2.  计费因子查不到时认为计费因子单价是0
3.  计费时长（范围为0-100，当计费时长不在范围内要认为是计费日志有问题，当成计费为 0 处理)
4.  输出按客户标识字典序升序排序

对于1，其实就是让我们去除客户的重复日志信息，而日志是否重复的判断标准是：

> 同一客户、同一计费因子、相同时间戳

因此根据第 2 到 n+1 行输入的日志信息，一旦后面的日志和前面的日志上面三要素相同，则后面的日志就是重复的，可以忽略。

具体去重实现，针对不同语言有不同办法，大家可以看下面源码的具体实现。

--------------------

对于2，即某个客户名下某个日志的计费因子不存在（即不存在于第 n+3 到 n+3+m 行），那么此时计费因子单价为0，即对应日志不产生费用。

--------------------

对于3，需要我们日志的计算时长进行范围判断，如果不在指定范围，则对应日志不产生费用。

--------------------

对于4，输出按客户标识字典序升序排序

#### JS算法源码 ####

#### Java算法源码 ####

import java.util.*;
    
    public class Main {
        static class Log {
            String custId;
            String timestamp;
            String factor;
            int duration;
    
            @Override
            public int hashCode() {
                // 日志中如果同一客户、同一计费因子、在相同时间戳上报多次话单只能计费一次，选先上报的日志计费
                // 因此若日志的客户表示、时间戳、计费因子三要素相同，则认为日志重复
                return custId.hashCode() + timestamp.hashCode() + factor.hashCode();
            }
    
            @Override
            public boolean equals(Object obj) {
                if (this == obj) {
                    return true;
                }
    
                if (obj == null || getClass() != obj.getClass()) {
                    return false;
                }
    
                Log log = (Log) obj;
                // 日志中如果同一客户、同一计费因子、在相同时间戳上报多次话单只能计费一次，选先上报的日志计费
                // 因此若日志的客户表示、时间戳、计费因子三要素相同，则认为日志重复
                return custId.equals(log.custId) && timestamp.equals(log.timestamp) && factor.equals(log.factor);
            }
        }
    
        public static void main(String[] args) {
            // 设置逗号和换行符作为读取分隔符
            Scanner sc = new Scanner(System.in).useDelimiter("[,\n]");
    
            // 计费日志的条数
            int n = sc.nextInt();
    
            // key是客户id，val是客户的计费日志
            HashMap<String, HashSet<Log>> logs = new HashMap<>();
    
            for (int i = 0; i < n; i++) {
                Log log = new Log();
    
                // 时间戳
                log.timestamp = sc.next();
                // 客户标识
                log.custId = sc.next();
                // 计费因子
                log.factor = sc.next();
                // 计费时长
                log.duration = sc.nextInt();
    
                logs.putIfAbsent(log.custId, new HashSet<>());
                logs.get(log.custId).add(log);
            }
    
            // 计费因子的数量
            int m = sc.nextInt();
    
            // key是计费因子，val是计费因子单价
            HashMap<String, Integer> unit_price = new HashMap<>();
    
            for (int i = 0; i < m; i++) {
                // 计费因子
                String factor = sc.next();
                // 单价
                int price = sc.nextInt();
    
                unit_price.put(factor, price);
            }
    
            // 客户花费,key是客户id，val是客户所有log的花费之和
            TreeMap<String, Integer> fees = new TreeMap<>(); // TreeMap会根据key的自然顺序进行排序，这里的key是custId字符串，自然顺序就是字典序升序
    
            for (String custId : logs.keySet()) {
                for (Log log : logs.get(custId)) {
                    // 计费时长（范围为0-100), 当计费时长不在范围内要认为是计费日志有问题，当成计费为 0 处理
                    if (log.duration > 100 || log.duration < 0) {
                        log.duration = 0;
                    }
    
                    // 计费因子查不到时认为计费因子单价是0
                    int price = unit_price.getOrDefault(log.factor, 0);
    
                    fees.put(custId, fees.getOrDefault(custId, 0) + log.duration * price);
                }
            }
    
            for (String custId : fees.keySet()) {
                System.out.println(custId + "," + fees.get(custId));
            }
    
        }
    }

#### Python算法源码 ####

# 算法入口
    def solution():
        # 计费日志的条数
        n = int(input())
    
        # key是客户id，val是客户的计费日志容器
        logs = {}
        for _ in range(n):
            # 时间戳,客户标识,计费因子,计费时长
            timestamp, custId, factor, duration = input().split(",")
    
            # 初始化客户的日志容器（对象作为容器）
            if custId not in logs:
                logs[custId] = {}
    
            key = timestamp + factor
    
            # 若日志的客户标识、时间戳、计费因子三要素相同，则认为日志重复，不加入重复日志
            if key in logs[custId]:
                continue
    
            # 日志不重复，则记录日志信息[计费因子，计费时长]
            logs[custId][key] = (factor, int(duration))
    
        # 计费因子的数量
        m = int(input())
    
        # key是计费因子，val是计费因子单价
        unit_price = {}
        for _ in range(m):
            # 计费因子,单价
            factor, price = input().split(",")
            unit_price[factor] = int(price)
    
        # 客户花费,key是客户id，val是客户所有log的花费之和
        fees = {}
    
        for custId in logs:
            for factor, duration in logs[custId].values():
                # 计费时长（范围为0-100), 当计费时长不在范围内要认为是计费日志有问题，当成计费为 0 处理
                if duration > 100 or duration < 0:
                    duration = 0
    
                # 计费因子查不到时认为计费因子单价是0
                price = unit_price.get(factor, 0)
    
                fees[custId] = fees.get(custId, 0) + price * duration
    
        # 结果按照客户标识（fees的key）进行升序
        for custId in sorted(fees.keys()):
            print(f"{custId},{fees[custId]}")
    
    
    # 算法调用
    solution()

#### C算法源码 ####

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_N 1000
    #define MAX_SIZE 20
    
    typedef struct {
        char *timestamp;
        char *custId;
        char *factor;
        int duration;
    } Log;
    
    Log *new_Log() {
        Log *log = (Log *) malloc(sizeof(Log));
    
        log->timestamp = (char *) calloc(MAX_SIZE, sizeof(char));
        log->custId = (char *) calloc(MAX_SIZE, sizeof(char));
        log->factor = (char *) calloc(MAX_SIZE, sizeof(char));
        log->duration = 0;
    
        return log;
    }
    
    typedef struct {
        char *custId;
        Log **logs;
        int logs_size;
        int fee;
    } Customer;
    
    Customer *new_Customer(char *custId) {
        Customer *customer = (Customer *) malloc(sizeof(Customer));
    
        customer->custId = (char *) calloc(MAX_SIZE, sizeof(char));
        strcpy(customer->custId, custId);
    
        customer->logs = (Log **) calloc(MAX_N, sizeof(Log *));
        customer->logs_size = 0;
    
        customer->fee = 0;
    
        return customer;
    }
    
    void add_Log(Customer *customer, Log *log) {
        for (int i = 0; i < customer->logs_size; i++) {
            char *custId = customer->logs[i]->custId;
            char *timestamp = customer->logs[i]->timestamp;
            char *factor = customer->logs[i]->factor;
    
            // 日志中如果同一客户、同一计费因子、在相同时间戳上报多次话单只能计费一次，选先上报的日志计费
            // 因此若日志的客户表示、时间戳、计费因子三要素相同，则认为日志重复
            if (strcmp(custId, log->custId) == 0 && strcmp(timestamp, log->timestamp) == 0 &&
                strcmp(factor, log->factor) == 0) {
                // 重复日志不加入
                return;
            }
        }
    
        // 不重复日志加入
        customer->logs[customer->logs_size++] = log;
    }
    
    int cmp(const void *a, const void *b) {
        Customer *A = *((Customer **) a);
        Customer *B = *((Customer **) b);
    
        return strcmp(A->custId, B->custId);
    }
    
    int main() {
        // 计费日志的条数
        int n;
        scanf("%d", &n);
    
        // 收集客户对象
        Customer *customers[MAX_N] = {NULL};
        int customers_size = 0;
    
        for (int i = 0; i < n; i++) {
            getchar();
    
            // 日志对象
            Log *log = new_Log();
            scanf("%[^,],%[^,],%[^,],%d", log->timestamp, log->custId, log->factor, &log->duration);
    
            // 检查该日志对应的客户是否已记录到customers数组
            int j = 0;
            for (; j < customers_size; j++) {
                if (strcmp(customers[j]->custId, log->custId) == 0) {
                    break;
                }
            }
    
            // 如果未记录过该客户，则新建该客户对象
            if (j == customers_size) {
                customers[customers_size++] = new_Customer(log->custId);
            }
    
            // 加入该日志到该客户对象中
            add_Log(customers[j], log);
        }
    
        // 计费因子的数量
        int m;
        scanf("%d", &m);
    
        for (int i = 0; i < m; i++) {
            getchar();
    
            // 计费因子
            char factor[MAX_SIZE];
            // 单价
            int price;
    
            scanf("%[^,],%d", factor, &price);
    
            // 遍历客户对象
            for (int j = 0; j < customers_size; j++) {
                Customer *customer = customers[j];
    
                // 遍历客户对象下的日志集合
                for (int k = 0; k < customer->logs_size; k++) {
                    Log *log = customer->logs[k];
    
                    // 如果该日志的计费因子和当前计费因子相同，则计算当前日志的花费，并求和到客户总费用fee中
                    // 注意：
                    // 1、计费时长（范围为0-100), 当计费时长不在范围内要认为是计费日志有问题，当成计费为 0 处理
                    // 2、计费因子查不到时认为计费因子单价是0
                    if (log->duration >= 0 && log->duration <= 100 && strcmp(log->factor, factor) == 0) {
                        customer->fee += log->duration * price;
                    }
                }
            }
        }
    
        // 结果按照客户标识进行升序
        qsort(customers, customers_size, sizeof(customers[0]), cmp);
    
        for (int i = 0; i < customers_size; i++) {
            printf("%s,%d\n", customers[i]->custId, customers[i]->fee);
        }
    
        return 0;
    }

#### C++算法源码 ####

#include <bits/stdc++.h>
    using namespace std;
    
    vector<string> splitCin(char delimiter) {
        string s;
        cin >> s;
    
        stringstream ss(s);
        string token;
    
        vector<string> res;
        while (getline(ss, token, delimiter)) {
            res.emplace_back(token);
        }
    
        return res;
    }
    
    int main() {
        // 计费日志的条数
        int n;
        cin >> n;
    
        // key是客户id，val是客户的计费日志
        map<string, map<string, vector<string>>> logs;
    
        for (int i = 0; i < n; i++) {
            vector<string> tmp = splitCin(',');
    
            // 时间戳
            string timestamp = tmp[0];
            // 客户标识
            string custId = tmp[1];
            // 计费因子
            string factor = tmp[2];
            // 计费时长
            string duration = tmp[3];
    
            if (logs.count(custId) == 0) {
                logs[custId] = map<string, vector<string>>();
            }
    
            // 若日志的客户标识、时间戳、计费因子三要素相同，则认为日志重复，不加入重复日志
            string key = timestamp + factor;
            if (logs[custId].count(key) > 0) {
                continue;
            }
    
            // 日志不重复，则记录日志信息[计费因子，计费时长]
            logs[custId][key] = vector<string>{factor, duration};
        }
    
        // 计费因子的数量
        int m;
        cin >> m;
    
        // key是计费因子，val是计费因子单价
        map<string, int> unit_price;
    
        for (int i = 0; i < m; i++) {
            vector<string> tmp = splitCin(',');
    
            // 计费因子
            string factor = tmp[0];
            // 单价
            string price = tmp[1];
    
            unit_price[factor] = stoi(price);
        }
    
        // 客户花费,key是客户id，val是客户所有log的花费之和
        map<string, int> fees;
    
        for (const auto &pair: logs) {
            string custId = pair.first;
    
            for (const auto &item: logs[custId]) {
                vector<string> log = item.second;
    
                string factor = log[0];
                int duration = stoi(log[1]);
    
                // 计费时长（范围为0-100), 当计费时长不在范围内要认为是计费日志有问题，当成计费为 0 处理
                if (duration > 100 || duration < 0) {
                    duration = 0;
                }
    
                // 计费因子查不到时认为计费因子单价是0
                int price = unit_price[factor];
    
                fees[custId] += duration * price;
            }
        }
    
        // 结果按照客户标识（fees的key）进行升序, map自动按照key升序
        for (const auto &pair: fees) {
            cout << pair.first << "," << pair.second << endl;
        }
    
        return 0;
    }

[- _ - HydroOJ]: https://hydro.ac/d/HWOCR/p/OCR029