c++ - 如何打印与特定值对应的元素的总和？

Question

我在处理这个问题时遇到了麻烦:
在第一行输入: int n - 交付到商店的包裹数量
然后在 n 行中: int a 和 int b - 产品的 ID 及其数量。
期望的输出:
第一行 - x，独特产品的数量。
然后在 x 行中: int a 和 int b - 产品的 ID 及其总量。
IE。:

input
6
2 1
3 11
1 4
3 2
7 1
2 1

output
4
2 2
3 13
1 4
7 1

我的代码:

#include <iostream>                                                             
using namespace std;                                                            

int a_tab[1000000] = {0};                                                       
int b_tab[1000000] = {0};                                                       

int main()                                                                      
{                                                                               
    ios_base::sync_with_stdio(false);                                           
    cin.tie(NULL);                                                              

    unsigned int a;                                                             
    unsigned short b;                                                           

    unsigned int n;                                                             
    cin >> n;                                                                   

    unsigned int counter = n;                                                   

    for (int i = 0; i < n; i++)                                                 
    {                                                                           
        cin >> a >> b;                                                          
        bool ax = false;                                                        
        for (int j = 0; j < i; j++)                                             
        {                                                                       
            if (a_tab[j] == a)                                                  
                {                                                               
                    b_tab[j] = b_tab[j] + b;                                    
                    ax = true;                                                  
                    counter--;                                                  
                    break;                                                      
                }                                                               
        }                                                                       
        if (ax == false)                                                        
        {                                                                       
            a_tab[i] = a;                                                       
            b_tab[i] = b;                                                       
        }                                                                       
        a = 0;                                                                  
        b = 0;                                                                  
    }                                                                           

        cout << counter << endl;                                                

        for (int i = 0; i < n; i++)                                             
    {                                                                           
        if (a_tab[i] > 0)                                                       

        {                                                                       
            cout << a_tab[i] << " " << b_tab[i] << endl;                        
        }                                                                       

    }                                                                           



    return 0;                                                                   
}

但看来，我的算法不正确，因为我遇到了 Time Limit Exceeded 错误。
提前感谢您的帮助。

Answer 1

我将向您展示针对您的问题的 C++ 解决方案。

如果这是某种竞争性编程问题(我怀疑这是因为您的陈述“超出时间限制”)，那么您可能需要在尝试学习“更脏”的编程时忘记这个解决方案。

对于您的任务，有一个更不标准的解决方案，您会在 SO 上找到至少 50 个类似的线程，描述类似的解决方案。

您需要使用 std::map或 std::unordered_map ，取决于您想要的输出。好像不需要排序，所以std::unordered_map是要走的路。

这两个容器都有一个下标运算符，它

如果元素已经在 map 中，则返回对该元素的引用，或

如果该元素不在 map 中，则创建一个新元素，然后返回对新元素的引用

因此，无论如何，我们都会获得对 map 中元素的引用。我们只需将数量添加到其中。就这样。

然后我们使用基于范围的 for 循环和结构化绑定(bind)输出结果。这也非常简单易懂。

请参见:

#include <iostream>
#include <sstream>
#include <unordered_map>

// I do not want to type all the type 
// So, I do read from this stream and not from std::cin
// if you want to read from std::cin, then replace sourceData with std::cin in function main
std::istringstream sourceData{ R"(6
2 1
3 11
1 4
3 2
7 1
2 1)" };


int main() {

    // Define the result
    std::unordered_map<unsigned, unsigned> result{};

    // Get the number of lines to read
    if (size_t numberOfLines; sourceData >> numberOfLines) {

        // Read all lines as specified by the user
        for (size_t n = 0U; n < numberOfLines; ++n) {

            // Read id and count
            if (unsigned a{}, b{}; sourceData >> a >> b) {

                // some up grouped by id
                result[a] += b;
            }
        }
    }
    // Show the number of resulting lines
    std::cout << result.size() << "\n";

    // Show the result, so the id and the summed up quantity
    for (const auto& [id, totalQuantity] : result) {
        std::cout << id << " " << totalQuantity << "\n";
    }

    return 0;
}