CodeForces - 1616A Integer Diversity【map】

A. Integer Diversity
time limit per test1 second
memory limit per test256 megabytes

You are given n integers a1,a2,…,an. You choose any subset of the given numbers (possibly, none or all numbers) and negate these numbers (i. e. change x→(−x)). What is the maximum number of different values in the array you can achieve?

Input
The first line of input contains one integer t (1≤t≤100): the number of test cases.

The next lines contain the description of the t test cases, two lines per a test case.

In the first line you are given one integer n (1≤n≤100): the number of integers in the array.

The second line contains n integers a1,a2,…,an (−100≤ai≤100).

Output
For each test case, print one integer: the maximum number of different elements in the array that you can achieve negating numbers in the array.

Example
input
3
4
1 1 2 2
3
1 2 3
2
0 0
output
4
3
1

Note
In the first example we can, for example, negate the first and the last numbers, achieving the array [−1,1,2,−2] with four different values.

In the second example all three numbers are already different.

In the third example negation does not change anything.

问题链接：CodeForces - 1616A Integer Diversity
问题简述：（略）
问题分析：给出2个题解，各有技巧不同。0算1次，0以外的绝对值最多算2次。

AC的C++语言程序如下：


#include 
#include 
#include 

using namespace std;

int main()
{
    int t, n, a;
    scanf("%d", &t);
    while (t--) {
        map m;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a);
            m[abs(a)]++;
        }

        int ans = 0;
        for (auto [x, y] : m)
            if (x == 0) ans++;
            else ans += min(2, y);

        printf("%dn", ans);
    }

    return 0;
}

AC的C++语言程序如下：


#include 
#include 
#include 

using namespace std;

int main()
{
    int t, n, a;
    scanf("%d", &t);
    while (t--) {
        map m;
        int cnt = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a);
            if (m[a]) {
                if (m[-a])
                    ;
                else
                    m[-a] = 1, cnt++;
            } else
                m[a] = 1, cnt++;
        }

        printf("%dn", cnt);
    }

    return 0;
}

CodeForces - 1616A Integer Diversity【map】

C/C++/C#相关栏目本月热门文章