2.1枚舉介紹和全排列枚舉

枚舉就是將所有答案的可能都跑過一次
若有時候答案的可能樹太多，會導致超時，在這個單元中，就要學習如何以合理的時間複雜度找到答案

枚舉簡單題目

給定一個數字$n(1\leq n\leq 10^3)$問可以湊成幾對$a, b$買足$a\times b = n$?

很直觀的做法，可以直接用$O(n^2)$的時間複雜度來完成

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
           if(i * j == n) {
                ans++;
           }
        }
    }
    cout << ans << endl;
    return 0;
}

現在更改題目，將$n$的範圍改成$1\leq n\leq 10^5$，再去跑這個程式碼時，會發現程式遲遲跑不出結果來，因為很明顯地，$O(n^2)$會超時
現在我們會有幾種想法
1. 以這個$n$的大小，必須要用$O(n)$的時間複雜度才可能完成
2. $a\times b = n$可以轉換成$a=\frac{n}{b}$
用以上這兩種想法，相信你就可以想出如何使用$O(n)$解出這題了

只需要枚舉$n$並看看$n\\ b$frac{n}{b}$使否整除即可

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(n % i == 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

這個單元大部分時間都在學習如何將時間複雜度藉由特別的方法，改進到合理的範圍

全排列枚舉

這種枚舉方法主要是要將所有排列都找出來，例如輸出所有$1~n$的排列

在algorithm這個標頭檔中，有一個很好用的工具，稱作next_permutation

他會將你給定的陣列找出下一個排列(以字典序排序)

使用方法：next_permutation(左界(L), 右界(R))，接下來他就會針對這個左閉右開的區間做排列

回傳值：若排列為字典序最大者，回傳0，反之，回傳1

全排列枚舉裸題：Ex201

記得要在上方引入algorithm標頭檔

全排列枚舉程式碼

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int v[n];
    for(int i = 0; i < n; i++) {
        v[i] = i + 1;
    }
    do {
        for(int i = 0; i < n; i++) {
            cout << v[i] << ' ';
        }
        cout << endl;
    } while(next_permutation(v, v + n));
    return 0;
}

全排列枚舉例題

題目連結：Ex202

題目敘述：總共有$n$個城市，每個城市位於$(x_i, y_i)$，兩個城市之間的距離如下$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$

Back to top