hrbust 1721 A + B = 0 map的应用

　　13级春季校赛的热身题，但优化后我的代码也超时了，后来看了看学长的解法，觉得最简单的还是map，再一次感受到了map的强大。

题目描述如下

Description

There is an integer set A. How many couples of a and b, which can make a+b=0(a∈A, b∈A，a<=b).

Input

There are multiple test cases. The first line is an integer T indicating for the number of test cases. The first line of each case is an integer n, standing for the number of integers in set A.

The second line is n integers in set A separated by space.

(1<=n<=100 000，|ai|<=1000 000 000)

Output

For each test case, output all the unique couples of a and b by the order of a from small to large.

If there is no such a situation, output "<empty>".

Output a blank line after each case.

Sample Input

-1 0 1 4 -1 -4

1 1 2

Sample Output

-4 4

-1 1

<empty>

　　map的遍历方式：使用迭代器，it->first指原集合的元素，it-second指映射集合的元素。这样仅用O(N)的复杂度就求出了答案，尽管map是c++封装好的函数，运行相对较慢。

对比数组来说，map的好处有很好的处理负值，能够容下更大的数字等等，代码如下：

#include<cstdio>

#include<map>

#include<cstring>

#include<iostream>

using namespace std;

int main()

{

    int n,t,b,mark;

    scanf("%d",&t);

    while(t--)

    {

        map<int,int>a;

        a.clear();

        mark = ;

        scanf("%d",&n);

        while(n--)

        {

            scanf("%d",&b);

            a[b]++;

        }

        map<int,int>::iterator it;

        for(it = a.begin(); it->first <  && it != a.end(); it++)

        {

            ///cout<<"first = "<<it->first<<endl;

            if(it->second)

            {

                ///cout<<"second = "<<it->second<<endl;

                if(a[-it->first])

                {

                    printf("%d %d\n",it->first,-it->first);

                    mark = ;

                }

            }

        }

        if(a[] >= )

        {

            cout<<"0 0"<<endl;

            mark = ;

        }

        if(mark == )

            printf("<empty>\n");

        printf("\n");

    }

}

巴特西

hrbust 1721 A + B = 0 map的应用

最新文章

热门文章