C語言詳解數(shù)據(jù)結(jié)構(gòu)與算法中枚舉和模擬及排序

更新時(shí)間：2022年04月12日 16:43:40 作者：小羊努力變強(qiáng)

枚舉和模擬其實(shí)是沒什么算法可言的，大多數(shù)都是按照題目意思去寫，這里提供快排和歸并的兩個(gè)模板，感興趣的朋友來看看吧

枚舉

連號區(qū)間數(shù)

來源：第四屆藍(lán)橋杯省賽C++B組,第四屆藍(lán)橋杯省賽JAVAB組

小明這些天一直在思考這樣一個(gè)奇怪而有趣的問題：

在 1∼N 的某個(gè)排列中有多少個(gè)連號區(qū)間呢？

這里所說的連號區(qū)間的定義是：

如果區(qū)間 [L,R] 里的所有元素（即此排列的第 L 個(gè)到第 R 個(gè)元素）遞增排序后能得到一個(gè)長度為 R−L+1 的“連續(xù)”數(shù)列，則稱這個(gè)區(qū)間連號區(qū)間。

當(dāng) N 很小的時(shí)候，小明可以很快地算出答案，但是當(dāng) N 變大的時(shí)候，問題就不是那么簡單了，現(xiàn)在小明需要你的幫助。

輸入格式
第一行是一個(gè)正整數(shù) N，表示排列的規(guī)模。

第二行是 N 個(gè)不同的數(shù)字 Pi，表示這 N 個(gè)數(shù)字的某一排列。

輸出格式
輸出一個(gè)整數(shù)，表示不同連號區(qū)間的數(shù)目。

數(shù)據(jù)范圍
1≤N≤10000,
1≤Pi≤N

輸入樣例1：

4
3 2 4 1

輸出樣例1：

7

輸入樣例2：

5
3 4 2 5 1

輸出樣例2：

9

樣例解釋
第一個(gè)用例中，有 7 個(gè)連號區(qū)間分別是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二個(gè)用例中，有 9 個(gè)連號區(qū)間分別是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

先來看暴力做法

先兩次for()循環(huán)，對給出的數(shù)排序，然后再對區(qū)間內(nèi)的數(shù)做判斷，如果連續(xù)的就res++。

#include <bits/stdc++.h>

using namespace std;

const int N=10010;

int a[N],bac[N];

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

    for(int i=1;i<=n;i++)
       for(int j=i;j<=n;j++){
            memcpy(bac,a,sizeof a); // 這里要把數(shù)組的初始狀態(tài)存在bac數(shù)組中，因?yàn)槊看蝧ort排序后，數(shù)組的順序會發(fā)生改變。
            sort(a+i,a+j+1);

            bool flag=true;
            for(int k=i;k<j;k++){ 
                if(a[k+1] - a[k] != 1){
                    flag=false;
                    break;
                }
            }

            if(flag) res++;
            memcpy(a,bac,sizeof a); // 還原數(shù)組a的初始狀態(tài)
        }
    cout << res << endl;
    return 0;
}

但是這道題暴力做法在藍(lán)橋杯中只能得60分，然后我們再來想一下怎么優(yōu)化？

這里設(shè)兩層循環(huán)，一層i表示左端點(diǎn)，第二層j表示右端點(diǎn)。如果要保持連續(xù)性的話那么有一個(gè)思路：因?yàn)槭沁B續(xù)的所以在所取的[l，r]范圍中尋找最大值，最小值。然后相減，最后和r-l（區(qū)間長度）作比較即可。除此之外當(dāng)l=r時(shí)也算作連續(xù)
即MAX-MIN==R-L

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, INF = 100000000;

int n;
int a[N];

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

    int res = 0;
    for (int i = 0; i < n; i ++ )   // 枚舉區(qū)間左端點(diǎn)
    {
        int minv = INF, maxv = -INF;
        for (int j = i; j < n; j ++ )   // 枚舉區(qū)間右端點(diǎn)
        {
            minv = min(minv, a[j]);
            maxv = max(maxv, a[j]);
            if (maxv - minv == j - i) res ++ ;
        }
    }

    cout << res << endl;

    return 0;
}

遞增三元組

來源：第九屆藍(lán)橋杯省賽C++B組,第九屆藍(lán)橋杯省賽JAVAB組

給定三個(gè)整數(shù)數(shù)組

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

請你統(tǒng)計(jì)有多少個(gè)三元組 (i,j,k) 滿足：

1≤i,j,k≤N
Ai<Bj<Ck
輸入格式
第一行包含一個(gè)整數(shù) N。

第二行包含 N 個(gè)整數(shù) A1,A2,…AN。

第三行包含 N 個(gè)整數(shù) B1,B2,…BN。

第四行包含 N 個(gè)整數(shù) C1,C2,…CN。

輸出格式
一個(gè)整數(shù)表示答案。

數(shù)據(jù)范圍
1≤N≤105,
0≤Ai,Bi,Ci≤105

輸入樣例：

3
1 1 1
2 2 2
3 3 3

輸出樣例：

27

首先考慮暴力做法，三個(gè)數(shù)組嵌套枚舉，O(n3)的時(shí)間復(fù)雜度，n≤105一定會超時(shí)，這里提供代碼，想試一下的可以試試

//暴力做法枚舉（會超時(shí)）
#include <bits/stdc++.h>

using namespace std;


const int N=10000;

int n,a[N],b[N],c[N];
int cnt=0;
int main(){
    //輸入
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    //運(yùn)算
    for(int i=0;i<n;i++)
    	for(int j=0;j<n;j++)
    		for(int k=0;k<n;k++)
        		if(a[i]<b[j]&&b[j]<c[k])
	            cnt++;
    cout<<cnt<<endl;
    return 0;
}

嘗試通過枚舉的次序進(jìn)行優(yōu)化本題，先枚舉B數(shù)組，在A中尋找小于B[i]的數(shù)的個(gè)數(shù)cnt1，在C中尋找大于B[i]的數(shù)的個(gè)數(shù)cnt2，帶有B[i]的合法選擇數(shù)就是cnt1*cnt2。

用暴力查找時(shí)間總的時(shí)間復(fù)雜度為O(n2)，還是會超時(shí)。

二分

既然是查找，那么可以考慮進(jìn)行二分查找，查找前先通過排序預(yù)處理三個(gè)數(shù)組，排序時(shí)間復(fù)雜度O(nlog2n)O(nlog2n),枚舉B的所有元素+查找A,C中的元素時(shí)間復(fù)雜度也是O(nlog2n)O(nlog2n)，總的時(shí)間復(fù)雜度降為O(nlog2n)

//二分查找
#include <bits/stdc++.h>

using namespace std;

const int N=100000+6;

int n,a[N],b[N],c[N];
long long res=0;
int main(){
    cin>>n;//輸入
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    //排序
    sort(a,a+n);sort(b,b+n);sort(c,c+n);
    //查找
    for(int i=0;i<n;i++)
    {
        int low_a=0,right_a=n-1;
        while(low_a<right_a)    //找比b[i]小的最后一個(gè)數(shù)
        {
            int mid=(low_a+right_a+1)>>1;//加1之后改為向上取整
            if(a[mid]<b[i])  low_a=mid;
            else  right_a=mid-1;
        }
        if(a[low_a]>=b[i]) low_a=-1;//所有數(shù)都大于等于b[i]的時(shí)候，low_a=-1,這樣最后(low_a+1)*(n-low_b)的時(shí)候?yàn)?

        int low_b=0,right_b=n-1;
        while(low_b<right_b)   //找比b[i]大的第一個(gè)數(shù)
        {
            int mid =(low_b+right_b)>>1;
            if(c[mid]>b[i]) right_b=mid;
            else low_b=mid+1;
        }
        if(c[low_b]<=b[i]) low_b=n;//所有數(shù)都小于等于b[i]的時(shí)候，low_b=n,這樣最后(low_a+1)*(n-low_b)的時(shí)候?yàn)?
        //if(low_a!=0&&low_b!=n-1)//最開始的時(shí)候用這種方法判斷，后來發(fā)現(xiàn)不行
         //如果只有一個(gè)數(shù)字可以的時(shí)候，這種情況無法判斷，
         // 例如：
         //  1 4 5
         //  5 5 9
         //  4 6 7（10）  當(dāng)b[i]=9的時(shí)候，c[i]=7和10的時(shí)候無法判斷
        res+=(long long)(low_a+1)*(n-low_b);

    }
    cout<<res<<endl;

    return 0;
}

雙指針

進(jìn)一步對查找進(jìn)行優(yōu)化，對于排過序的數(shù)組A和B，尋找A中小于B[i]的元素的個(gè)數(shù)可以考慮雙指針?biāo)惴?，因?yàn)槊總€(gè)指針最多移動n次，故查找的時(shí)間復(fù)雜度降到O(n)，查找C與查找A同理，只是找第一個(gè)大于B的位置。

只需要將上述二分程序中的

//二分
for(int i = 1; i <= n; ++i) {
    int key = num[1][i];
    //A中二分查找第一個(gè)小于key的數(shù)的下標(biāo)
    int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
    //C中二分查找第一個(gè)大于key的數(shù)的下標(biāo)
    int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
    if(pos1 >= 1 && pos2 <= n) {
        ans += (LL)pos1*(n-pos2+1);
    }
}

更改為

//雙指針
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {
    int key = num[1][i];
    while(a<=n && num[0][a] < key) a++;
    while(c<=n && num[2][c] <= key) c++;

    ans += (LL)(a-1)*(n-c+1);
}

完整的雙指針程序?yàn)椋?/p>

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int num[3][N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3; ++i) 
        for(int j = 1; j <= n; ++j) 
            scanf("%d", &num[i][j]);
    for(int i = 0; i < 3; ++i)
        sort(num[i]+1, num[i]+n+1);

    LL ans = 0;
    //枚舉B，尋找A滿足的個(gè)數(shù)以及C滿足的個(gè)數(shù)相乘
    int a = 1, c = 1;
    for(int i = 1; i <= n; ++i) {
        int key = num[1][i];
        while(a<=n && num[0][a] < key) a++;
        while(c<=n && num[2][c] <= key) c++;

        ans += (LL)(a-1)*(n-c+1);

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

前綴和

之前的雙指針?biāo)惴〞r(shí)間復(fù)雜度的瓶頸為：排序O(nlog2n)O(nlog2n)

考慮是否可以不排序在O(n)的時(shí)間內(nèi)解決此問題呢？

既然要排序?qū)崿F(xiàn)快速的查找A中小于B[i]的數(shù)的個(gè)數(shù)，可以將數(shù)組A中所有元素出現(xiàn)的次數(shù)存入一個(gè)哈希表中，因?yàn)閿?shù)組中元素的范圍只有n5n5, 可以開一個(gè)大的數(shù)組cnta 作為哈希表。

在枚舉B中元素時(shí)，我們需要快速查找找小于B[i]的所有元素的總數(shù)，只需要在枚舉之前先將求出表中各數(shù)的前綴和即可。

查找C與查找A同理可得。

//前綴和
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5+10;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];

int main() {
    int n;
    scanf("%d", &n);
    //獲取數(shù)i在A中有cntc[i]個(gè)，并對cnt求前綴和sa
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
        cnta[++A[i]]++;
    }
    sa[0] = cnta[0];
    for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i];
    //B只讀取即可
    for(int i = 1; i <= n; ++i) scanf("%d", &B[i]), B[i]++;

    //獲取數(shù)i在C中有cntc[i]個(gè)，并對cnt求前綴和sc
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &C[i]);
        cntc[++C[i]]++;
    }
    sc[0] = cntc[0];
    for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i]; 

    //遍歷B求解
    LL ans = 0;
    for(int i = 1; i <= n; ++i) {
        int b = B[i];
        ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);
    }
    cout<<ans<<endl;
    return 0;
}

在這里插入圖片描述

分別是暴力，前綴和，雙指針，二分。

模擬

特別數(shù)的和

來源：第十屆藍(lán)橋杯省賽C++B組,第十屆藍(lán)橋杯省賽JAVAB組

小明對數(shù)位中含有 2、0、1、9 的數(shù)字很感興趣（不包括前導(dǎo) 0），在 1 到 40 中這樣的數(shù)包括 1、2、9、10 至 32、39 和 40，共 28 個(gè)，他們的和是 574。

請問，在 1 到 n 中，所有這樣的數(shù)的和是多少？

輸入格式
共一行，包含一個(gè)整數(shù) n。

輸出格式
共一行，包含一個(gè)整數(shù)，表示滿足條件的數(shù)的和。

數(shù)據(jù)范圍
1≤n≤10000

輸入樣例：

40

輸出樣例：

574

常用小技巧：關(guān)于取出x的每位數(shù)字和將字符數(shù)字轉(zhuǎn)為數(shù)字

1.取出x的每位數(shù)字
int t = x % 10;
x /= 10;
2.將字符數(shù)字轉(zhuǎn)為數(shù)字
int x = 0;
for (int i = 0; i < str.size(); i ++ )
x = x * 10 + str[i] - '0';

下面請看你代碼：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x = i;
        while (x)
        {
            int t = x % 10; // 取出x的個(gè)位
            x /= 10;    // 刪掉x的個(gè)位
            if (t == 2 || t == 0 || t == 1 || t == 9)
            {
                res += i;
                break;
            }
        }
    }

    cout << res << endl;

    return 0;
}

錯誤票據(jù)

來源：第四屆藍(lán)橋杯省賽C++A/B組,第四屆藍(lán)橋杯省賽JAVAA/B組

某涉密單位下發(fā)了某種票據(jù)，并要在年終全部收回。

每張票據(jù)有唯一的ID號。

全年所有票據(jù)的ID號是連續(xù)的，但I(xiàn)D的開始數(shù)碼是隨機(jī)選定的。

因?yàn)楣ぷ魅藛T疏忽，在錄入ID號的時(shí)候發(fā)生了一處錯誤，造成了某個(gè)ID斷號，另外一個(gè)ID重號。

你的任務(wù)是通過編程，找出斷號的ID和重號的ID。

假設(shè)斷號不可能發(fā)生在最大和最小號。

輸入格式
第一行包含整數(shù) N，表示后面共有 N 行數(shù)據(jù)。

接下來 N 行，每行包含空格分開的若干個(gè)（不大于100個(gè)）正整數(shù)（不大于100000），每個(gè)整數(shù)代表一個(gè)ID號。

輸出格式
要求程序輸出1行，含兩個(gè)整數(shù) m,n，用空格分隔。

其中，m表示斷號ID，n表示重號ID。

數(shù)據(jù)范圍
1≤N≤100

輸入樣例：

2
5 6 8 11 9
10 12 9

輸出樣例：

7 9

思路

找出最大和最小的數(shù)，同時(shí)再用一個(gè)數(shù)組記錄每個(gè)數(shù)字的個(gè)數(shù)，最后遍歷一遍即可

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;
    string line;

    getline(cin, line); // 忽略掉第一行的回車
    while (cnt -- )
    {
        getline(cin, line);
        stringstream ssin(line);

        while (ssin >> a[n]) n ++ ;
    }

    sort(a, a + n);

    int res1, res2;
    for (int i = 1; i < n; i ++ )
        if (a[i] == a[i - 1]) res2 = a[i];  // 重號
        else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 斷號

    cout << res1 << ' ' << res2 << endl;

    return 0;
}

排序

快速排序

給定你一個(gè)長度為 n 的整數(shù)數(shù)列。

請你使用快速排序?qū)@個(gè)數(shù)列按照從小到大進(jìn)行排序。

并將排好序的數(shù)列按順序輸出。

輸入格式
輸入共兩行，第一行包含整數(shù) n。

第二行包含 n 個(gè)整數(shù)（所有整數(shù)均在 1∼109 范圍內(nèi)），表示整個(gè)數(shù)列。

輸出格式
輸出共一行，包含 n 個(gè)整數(shù)，表示排好序的數(shù)列。

數(shù)據(jù)范圍
1≤n≤100000

輸入樣例：

5
3 1 2 4 5

輸出樣例：

1 2 3 4 5

快排思路

1.有數(shù)組 q, 左端點(diǎn) l, 右端點(diǎn)r

2.確定劃分邊界 x

3.將 q 分為 <=x 和 >=x 的兩個(gè)小數(shù)組
       i 的含義: i 之前的元素都 ≤x, 即 q[l..i−1]q[l..i−1] ≤x
       j 的含義: j 之后的元素都 ≥x, 即 q[j+1..r]q[j+1..r] ≥x
       結(jié)論: while循環(huán)結(jié)束后, q[l..j] ≤x,q[j+1..r] ≥x
       簡單不嚴(yán)謹(jǐn)證明:
       while 循環(huán)結(jié)束時(shí), i≥j
       若 i>j , 顯然成立
       若 i=ji=j
       ∵ 最后一輪循環(huán)中兩個(gè) do−whiledo−while 循環(huán)條件都不成立
       ∴ q[i]≥x,q[j]≤x
       ∴ q[i]=q[j]=x
       ∴ 結(jié)論成立

4.遞歸處理兩個(gè)小數(shù)組

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

歸并排序

歸并的題和快排的題是一樣的，這里就不寫題目了。

歸并思路

1.有數(shù)組 q, 左端點(diǎn) l, 右端點(diǎn) r

2.確定劃分邊界 mid

3.遞歸處理子問題 q[l..mid], q[mid+1..r]

4.合并子問題

   主體合并
       至少有一個(gè)小數(shù)組添加到 tmp 數(shù)組中
   收尾
       可能存在的剩下的一個(gè)小數(shù)組的尾部直接添加到 tmp 數(shù)組中
   復(fù)制回來
       tmp 數(shù)組覆蓋原數(shù)組

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

到此這篇關(guān)于C語言詳解數(shù)據(jù)結(jié)構(gòu)與算法中枚舉和模擬及排序的文章就介紹到這了,更多相關(guān)C語言枚舉模擬排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: