题目分析与思路提示

1. 解题思路

这道题是典型的 “统计 + 排序” 问题。

• 步骤一：数据存储与合并

  • 我们需要存储每一类货物的名称和总数量。可以使用一个结构体 (struct) 来表示一种货物。
  • 由于 $N$ 只有 1000，我们可以使用一个结构体数组（或 vector）来存储已经整理好的货物。
  • 处理流程：
    1. 读入一条新记录 (name, count)。
    2. 遍历当前已经存好的结构体数组，查找是否已经存在该 name。
    3. 如果存在：直接将 count 累加到对应的结构体中。
    4. 如果不存在：这是一个新物种，向结构体数组中添加一个新元素 (name, count)。

• 步骤二：排序

  • GESP 5级要求掌握 std::sort 函数以及自定义比较函数（cmp）。
  • 我们需要写一个 cmp 函数，规则如下：

    bool cmp(const Item &a, const Item &b) {
        if (a.count != b.count) {
            return a.count > b.count; // 数量不同，大的排前面
        } else {
            return a.name < b.name;   // 数量相同，字典序小的排前面
        }
    }
    

2. 复杂度分析

• 合并阶段：对于 $N$ 条记录，每条记录最坏需要遍历当前已有的所有种类。最坏情况下有 $N$ 种货物，复杂度为 $O(N^2)$。由于 $N=1000$，$N^2 = 10^6$，在计算机 1 秒可处理 $10^8$ 次运算的能力下，这是非常快的。
• 排序阶段：使用快排，复杂度 $O(K \log K)$，其中 $K$ 是不同货物的种类数（$K \le N$）。
• 总复杂度：$O(N^2)$，完全符合要求。

参考代码 (C++14)

/**
 * 题目：丝路商队的账簿
 * 难度：GESP 5级
 * 知识点：结构体、字符串、线性查找合并、自定义排序
 */

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // 包含 sort

using namespace std;

// 定义结构体存储货物信息
struct Goods {
    string name;
    int total_count;
};

// 自定义比较函数
// 规则：数量从大到小；如果数量相同，名称字典序从小到大
bool cmp(const Goods &a, const Goods &b) {
    if (a.total_count != b.total_count) {
        return a.total_count > b.total_count; // 降序
    }
    return a.name < b.name; // 升序
}

int main() {
    // 提升 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    // 用于存储合并后的货物
    vector<Goods> ledger;

    for (int i = 0; i < N; ++i) {
        string s;
        int c;
        cin >> s >> c;

        // 在 ledger 中查找是否已存在该货物
        bool found = false;
        for (int j = 0; j < ledger.size(); ++j) {
            if (ledger[j].name == s) {
                // 找到了，累加数量
                ledger[j].total_count += c;
                found = true;
                break;
            }
        }

        // 如果没找到，说明是新货物，添加进去
        if (!found) {
            ledger.push_back({s, c});
        }
    }

    // 排序
    sort(ledger.begin(), ledger.end(), cmp);

    // 输出结果
    for (int i = 0; i < ledger.size(); ++i) {
        cout << ledger[i].name << " " << ledger[i].total_count << endl;
    }

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <map>

using namespace std;

// 货物结构体
struct Goods {
    string name;
    int total_count;
};

// 比较函数
bool cmp(const Goods &a, const Goods &b) {
    if (a.total_count != b.total_count) {
        return a.total_count > b.total_count;
    }
    return a.name < b.name;
}

// 标准解法生成 .out
void solve(int N, const vector<pair<string, int>>& inputs, ofstream& fout) {
    // 为了生成器代码简便，这里可以用 map 来辅助合并（虽然题目解法推荐用线性扫描）
    // 但为了保证逻辑一致性，我们还是用 vector 实现
    vector<Goods> ledger;
    for (const auto& item : inputs) {
        bool found = false;
        for (auto& g : ledger) {
            if (g.name == item.first) {
                g.total_count += item.second;
                found = true;
                break;
            }
        }
        if (!found) {
            ledger.push_back({item.first, item.second});
        }
    }
    sort(ledger.begin(), ledger.end(), cmp);
    for (const auto& g : ledger) {
        fout << g.name << " " << g.total_count << endl;
    }
}

// 随机字符串生成
string randString(int len) {
    string s = "";
    for (int i = 0; i < len; ++i) {
        s += (char)('a' + rand() % 26);
    }
    return s;
}

int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    // 丝路常见货物名称池，用于构造更有真实感的数据
    vector<string> pool = {"silk", "tea", "china", "grape", "horse", "alfalfa", "jade", "glass", "gold", "spice", "carpet", "walnut", "sesame", "garlic", "cucumber"};

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N;
        vector<pair<string, int>> inputs;

        if (i == 1) { // 样例1
            N = 6;
            inputs = {{"grape",50}, {"horse",10}, {"grape",30}, {"alfalfa",100}, {"horse",5}, {"jade",2}};
        }
        else if (i == 2) { // 样例2 (同数量测试排序)
            N = 5;
            inputs = {{"silk",10}, {"tea",20}, {"silk",10}, {"jade",20}, {"gold",5}};
        }
        else if (i == 3) { // 全部相同
            N = 20;
            for(int k=0; k<N; k++) inputs.push_back({"silk", 1});
        }
        else if (i == 4) { // 全部不同
            N = 20;
            for(int k=0; k<N; k++) inputs.push_back({randString(5), randRange(1, 100)});
        }
        else if (i <= 7) { // 少量重复，使用名称池
            N = 100;
            for(int k=0; k<N; k++) {
                string name = pool[rand() % pool.size()];
                int count = randRange(1, 50);
                inputs.push_back({name, count});
            }
        }
        else { // 大规模随机
            N = 1000;
            int pool_size = (i == 10) ? 50 : 200; // Case 10 重复率高， Case 8,9 重复率低
            vector<string> big_pool;
            for(int p=0; p<pool_size; p++) big_pool.push_back(randString(randRange(3, 8)));
            
            for(int k=0; k<N; k++) {
                string name = big_pool[rand() % big_pool.size()];
                int count = randRange(1, 1000);
                inputs.push_back({name, count});
            }
        }

        // 写入输入
        fin << N << endl;
        for (const auto& item : inputs) {
            fin << item.first << " " << item.second << endl;
        }

        // 写入输出
        solve(N, inputs, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    return 0;
}