题面描述:

该程序用于计算基于云服务的客户话单总费用。输入包括计费日志的条数、每条日志的时间戳、客户标识、计费因子和计费时长，以及各种计费因子的单价列表。程序会确保同一客户在相同时间戳上报的同一计费因子只计费一次，且若计费时长不在0到100的范围内，则视为0。最后，输出每个客户的总费用，并按客户标识的字典序进行排序。

思路

1.先按照 ',' 分割，存储下所有的不重复的 (时间戳+客户标识+计费因子) 对应的价格

2.对于客户标识的字典序进行排序

3.按顺序计算每个客户的价格之和并输出

时间复杂度：$O(nlog n)$ ，瓶颈在于排序

题解

该程序旨在根据云服务的计费日志计算每个客户的总费用。输入包括多个计费日志，每个日志包含时间戳、客户标识、计费因子和计费时长，以及各计费因子的单价。为了确保费用的准确性，程序将同一客户在相同时间戳和计费因子的日志仅计费一次，并对计费时长进行范围校验（在0到100之间）。最终，程序将输出每个客户的总费用，按照客户标识的字典序进行排序。

程序的时间复杂度为$O(nlogn)$，主要瓶颈在于对客户标识的排序过程。

代码逻辑概述

1. 输入读取：程序首先读取计费日志的数量及其内容，接着读取计费因子的数量和对应的单价。
2. 数据结构：
   • 使用嵌套的 map 来存储每个客户的计费因子及累计的时长。
   • 使用单独的 map 存储计费因子的单价。
3. 计费逻辑：遍历每条日志，校验时长有效性并更新客户的计费因子时长。随后根据计费因子的单价计算客户的总费用。
4. 输出：按客户标识字典序输出每个客户的总费用，格式为 客户标识,总费用。

代码

python

n = int(input())
# 用来记录某个客户在某个因子上的总大小
infos = {}
st = set() # 用来记录已经处理过的日志
for i in range(n):
    time_stamp,client_name,factor_name,num = input().split(",")
    info = f'{time_stamp},{client_name},{factor_name}'
    # 日志中如果同一客户同一计费因子在相同时间戳上报多次话单只能计费一次，选先上报的日志计费
    # 所以后来的日志不用再处理
    if info in st:
        continue
    st.add(info)
    # 用字典来记录客户在某个因子上的总大小
    infos[client_name] = infos.get(client_name,{})
    # 如果因子大小在0-100之间，才记录
    if 0<=int(num)<=100:
        infos[client_name][factor_name] = infos[client_name].get(factor_name,0) + int(num)
m = int(input())
# 用字典来记录因子的单价
factor_infos = {}
for _ in range(m):
    factor_name,num = input().split(",")
    factor_infos[factor_name] = int(num)
# 按客户名字排序
keys = list(infos.keys())
keys.sort()
# 计算每个客户的总价格
for client_name in keys:
    total_price = 0
    for factor_name in infos[client_name]:
        if factor_name in factor_infos :
            total_price+= infos[client_name][factor_name] * factor_infos[factor_name]
    print(f"{client_name},{total_price}")

c++

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    int n; 
    cin >> n;  // 读取计费日志的数量
    map<string, map<string, int>> mp;  // 存储每个客户的计费因子及对应的累计时长
    string str;
    vector<vector<string>> table(n, vector<string>());  // 存储每条日志的信息

    // 读取计费日志
    for (int i = 0; i < n; i++) {
        cin >> str;  // 读取一行日志
        stringstream s(str);
        string line;
        while (getline(s, line, ',')) {
            table[i].push_back(line);  // 按逗号分割并存储到table中
        }
    }

    int m; 
    cin >> m;  // 读取计费因子的数量
    map<string, int> value;  // 存储每个计费因子的单价
    string v;
    vector<vector<string>> table1(m, vector<string>());  // 存储计费因子信息

    // 读取计费因子的单价
    for (int j = 0; j < m; j++) {
        cin >> v;  // 读取一行计费因子信息
        stringstream ss(v);
        string line;
        while (getline(ss, line, ',')) {
            table1[j].push_back(line);  // 按逗号分割并存储到table1中
        }
    }

    // 处理计费日志
    for (int i = 0; i < n; i++) {
        int cur = stoi(table[i][3]);  // 获取计费时长并转换为整数
        if (cur >= 0 && cur <= 100) {  // 校验计费时长的有效性
            mp[table[i][1]][table[i][2]] += cur;  // 累加有效的计费时长
        } else {
            mp[table[i][1]][table[i][2]] += 0;  // 无效时长处理
        }
    }

    // 处理计费因子的单价
    for (int j = 0; j < m; j++) {
        value[table1[j][0]] = stoi(table1[j][1]);  // 存储计费因子的单价
    }

    int num = mp.size();  // 客户数量
    int t = 0;  // 用于控制输出格式
    // 遍历每个客户及其计费因子
    for (auto &m : mp) {
        int res = 0;  // 存储当前客户的总费用
        t++;
        for (auto &p : m.second) {
            // 检查计费因子是否存在于价格列表中
            if (value.count(p.first)) {
                res += p.second * value[p.first];  // 计算费用
            }
        }
        cout << m.first << ',' << res;  // 输出客户标识和总费用
        if (t != num) cout << endl;  // 控制换行，最后一行不换行
    }
    return 0;
}

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // 读取计费日志的数量
        int n = Integer.parseInt(in.nextLine());
        
        // 用于存储唯一的计费日志头部（时间戳 + 客户标识 + 计费因子）
        Set<String> heads = new HashSet<>();
        
        // 存储每个客户的总费用
        Map<String, Integer> ans = new HashMap<>();
        
        // 存储日志
        List<String> logs = new ArrayList<>();

        // 读取计费日志并去重
        for (int i = 0; i < n; i++) {
            String line = in.nextLine();  // 读取一行计费日志
            // 获取日志的头部（即前3个字段：时间戳、客户标识、计费因子）
            String head = line.substring(0, line.lastIndexOf(","));
            
            // 如果头部已经存在，则跳过该日志
            if (heads.contains(head)) continue;
            
            // 保存日志和头部信息
            logs.add(line);
            heads.add(head);
        }

        // 存储计费因子的单价
        Map<String, Integer> factor = new HashMap<>();
        int m = Integer.parseInt(in.nextLine());  // 读取计费因子的数量
        
        // 读取计费因子及其对应的单价
        for (int i = 0; i < m; i++) {
            String line = in.nextLine();
            String[] fac = line.split(",");  // 按逗号分割
            factor.put(fac[0], Integer.parseInt(fac[1]));  // 保存计费因子及单价
        }

        // 计算每个客户的费用
        for (String line : logs) {
            String[] log = line.split(",");  // 按逗号分割日志
            String client = log[1];           // 客户标识
            String fac = log[2];              // 计费因子
            int number = Integer.parseInt(log[3]);  // 计费时长
            
            // 校验计费时长，若不在有效范围则设为0
            if (number <= 0 || number > 100) number = 0;
            
            // 计算当前日志的费用
            int bill = number * factor.getOrDefault(fac, 0);
            // 更新客户的总费用
            ans.put(client, ans.getOrDefault(client, 0) + bill);
        }

        // 对客户的费用进行排序
        List<Map.Entry<String, Integer>> sortedList = new ArrayList<>(ans.entrySet());
        Collections.sort(sortedList, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o1.getKey().compareTo(o2.getKey());  // 按客户标识的字典序排序
            }
        });

        // 输出每个客户及其总费用
        for (Map.Entry<String, Integer> entry : sortedList) {
            System.out.println(entry.getKey() + "," + entry.getValue());
        }
        
        // 关闭扫描器
        in.close();
    }
}

javascript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // 读取计费日志的数量
    let n = parseInt(await readline());

    // 用于存储唯一的计费日志头部（时间戳 + 客户标识 + 计费因子）
    let heads = new Set();
    
    // 存储每个客户的总费用
    let ans = new Map();
    
    // 存储日志
    let logs = [];

    // 读取计费日志并去重
    for (let i = 0; i < n; i++) {
        let line = await readline(); // 读取一行日志
        let head = line.substring(0, line.lastIndexOf(",")); // 获取日志的头部
        
        if (heads.has(head)) continue; // 如果头部已存在，则跳过
        logs.push(line); // 存储日志
        heads.add(head); // 记录头部信息
    }

    // 读取计费因子的数量
    let m = parseInt(await readline());
    
    // 存储计费因子的单价
    let factor = new Map();

    // 读取计费因子及其单价
    for (let i = 0; i < m; i++) {
        let line = await readline();
        let [fac, price] = line.split(",");
        factor.set(fac, parseInt(price));
    }

    // 计算每个客户的费用
    for (let line of logs) {
        let [timestamp, client, fac, number] = line.split(",");
        number = parseInt(number); // 计费时长

        // 校验计费时长，若不在有效范围则设为 0
        if (number <= 0 || number > 100) number = 0;

        // 计算当前日志的费用
        let bill = number * (factor.get(fac) || 0);
        ans.set(client, (ans.get(client) || 0) + bill);
    }

    // 对客户按标识进行字典序排序
    let sortedClients = [...ans.entries()].sort((a, b) => a[0].localeCompare(b[0]));

    // 输出每个客户及其总费用
    for (let [client, total] of sortedClients) {
        console.log(`${client},${total}`);
    }

    rl.close();
})();

编写一个程序为基云服务计算客户话单，输入为某云服务的计费日志和各种计费因子的计费单价的列表，计费日志内容包含时间戳、客户标识、计费因子、计费时长4个字段。日志中如果同一客户同一计费因子在相同时间戳上报多次话单只能计费一次，选先上报的日志计费。计算每个客户的话单总费用。

输入描述

第1行表示计费日志的条数$n$，是一个正整数，范围是$1\le n\le 1000$

第2到$n+1$行表示云服务的计费日志，共4列，第1列表示时间(是一个数字字符串，长度为10)、第2列表示客户标识(是一个字符串，长度为1~16)、第3列表示计费因子(是一个字符串，长度为1~16，计费因子查不到时认为计费因子单价是0)、第4列表示计费时长(范围为0~100，当计费时长不在范围内要认为是计费日志有问题，当成计费时长为0处理)，这4个字段使用逗号分隔 第$n+2$行表示计费因子的数量$m$，$m$是一个正整数，范围是$1\le m\le 100$

第$n+3$到$n+3+m$行表示各种计费因子的计费单价的列表，该表有2列，第1列表示计费因子(是一个字符串，长度为1~16)，第2列表示单价(是一个正整数，范围为1~100)，这2个字段使用逗号分

输出描述

每个客户的话单总费用,共2列，第1列表示客户名，第2列表示话单费用，2列用逗号分割，输出按客户标识字典序升序排序

样例1

输入

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= 15x5+8x7=131
client2= 0x5+35x7=245