什么是枚举

枚举就是不断猜测答案，从可能的集合（数组、链表……）尝试，再判断枚举出的数据是否与题目要求相符。

重点

  1. 枚举是注意要枚举哪些可能的情况、要素

  2. 未必需要枚举全部范围，不要浪费时间复杂度

  3. 注意枚举顺序

例题

给定一个长度为$N(1≤N≤10000)$的数组，其所有元素互不相同且均不为 0。求该数组中和为 0 的数对个数。

先进行输入。

1
2
3
cin >> n;
for(int i = 1; i <= n; ++i)
        cin >> a[i];

题目要求求出和为 0 的数对的个数，那么就枚举这两个数，判断这两个数是否为 0 即可。

优化：题中没要求数对是有序的，答案就是有序的情况的两倍（考虑如果 (a, b) 是答案，那么 (b, a) 也是答案）。对于这种情况，只需统计人为要求有顺序之后的答案，最后再乘上 2 就好了。

1
2
3
4
5
for(int i = 1; i <= n; ++i)
    for(int j = i + 1; j <= n; ++j) 
        if(a[i] + a[j] == 0)
            ans++;
ans *= 2;

时间复杂度：$O(n^2)$

已经足够题目要求了。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], n, ans = 0;

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j) 
            if(a[i] + a[j] == 0)
                ans++;
    ans *= 2;

    cout << ans << endl;
    return 0;
}

拓展练习