n = int(input())
data = [input().split(',') for _ in range(n)]
m = int(input())
factors = [input().split(',') for _ in range(m)]
factors_dict = {}
for line in factors:
    factors_dict[line[0]] =int(line[1])
for line in data:
    tmp = line[0]
    line[0] = line[1]
    line[1] = tmp
data.sort()
sum_dict = {}
st = set()
for line in data:
    name = line[0]
    time = line[1]
    factor = factors_dict.get(line[2],0)
    t = int(line[3])
    info = f"{name},{time},{factor}"     #用集合来判断是否出现过
    if info in st:
        continue
    st.add(info)
    if t<0 or t>100:
        t = 0
    if name not in sum_dict:
        sum_dict[name]=factor*t
    else:
        sum_dict[name]+=factor*t
for name,total in sum_dict.items():
    print(f"{name},{total}")


    

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

struct singlelog{ //用结构体表示一个物品的所有信息
    string timestamp;
    string clientname;
    string factorname;
    int n;

    singlelog(string timestamp_, string clientname_, string factorname_, int n_):
    timestamp(timestamp_), clientname(clientname_), factorname(factorname_), n(n_){};
};

bool notexists(const vector<singlelog> &vec, string timestamp_, string clientname_, string factorname_) //自定义判断物品的信息是否是已经存在
                                                                                                        //或者满足某种条件
{
    for(const auto &it:vec)
    {
        if(it.timestamp == timestamp_ && it.clientname == clientname_ && it.factorname == factorname_) 
        return false;
    }
    return true;
}

int main()
{
    int total_log_number; cin >> total_log_number;
    vector<singlelog> log;
    map<string, int> outputlist;
    for(int i = 0; i < total_log_number; ++i)
    {
        string wholelog; cin >> wholelog;
        int a = wholelog.find(',');
        string timestamp_ = wholelog.substr(0, a);
        wholelog = wholelog.substr(a + 1);
        int b = wholelog.find(',');
        string clientname_ = wholelog.substr(0, b);
        wholelog = wholelog.substr(b + 1);
        int c = wholelog.find(',');
        string factorname_ = wholelog.substr(0, c);
        wholelog = wholelog.substr(c + 1);
        int n_ = stoi(wholelog);
        if(notexists(log, timestamp_, clientname_, factorname_))
        {
            if(n_ >= 0 && n_ <=100)
            {
                singlelog currentlog(timestamp_, clientname_, factorname_, n_);
                log.push_back(currentlog);
            }
            else
            {
                singlelog currentlog(timestamp_, clientname_, factorname_, 0); //注意当时长不满足条件，不是不输入这一条，而是让时常置为0再输入
                log.push_back(currentlog);
            }
            if(outputlist.find(clientname_) == outputlist.end())
            {
                outputlist[clientname_] = 0;
            }
        }  
    }

    int factornumber; cin >> factornumber;
    map<string, int> factorlist;
    for(int i = 0; i < factornumber; ++i)
    {
        string factorinformation; cin >> factorinformation;
        int a = factorinformation.find(',');
        string factor = factorinformation.substr(0, a);
        factorinformation = factorinformation.substr(a + 1);
        int price = stoi(factorinformation);
        factorlist[factor] = price;
    }

    for(size_t i = 0; i < log.size(); ++i)
    {
        if(factorlist.find(log[i].factorname) != factorlist.end())
        {
            outputlist[log[i].clientname] += factorlist[log[i].factorname] * log[i].n; //计算每个用户花多少钱
        }
    }

    for(const auto &it:outputlist)
    {
        cout << it.first << "," << it.second << endl;
    }
}

from collections import defaultdict

n = int(input())
mapp = []
for _ in range(n):
    time, uid, factor, duration = list(input().split(","))
    duration = int(duration)
    if duration < 0 or duration > 100:
        duration = 0
    mapp.append([uid, factor, time, duration])
m = int(input())
factors = {}
for _ in range(m):
    factor, value = list(input().split(","))
    factors[factor] = int(value)

s = set()
client = defaultdict(int)
for x in mapp:
    uid, factor, time, duration = x
    if (uid, factor, time) in s:
        continue
    s.add((uid, factor, time))
    client[uid] += factors.get(factor, 0) * duration

client = sorted(client.items())

for x, y in client:
    print(x,end = ",")
    print(y)

题面描述:

该程序用于计算基于云服务的客户话单总费用。输入包括计费日志的条数、每条日志的时间戳、客户标识、计费因子和计费时长，以及各种计费因子的单价列表。程序会确保同一客户在相同时间戳上报的同一计费因子只计费一次，且若计费时长不在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();
    }
}