C语言数据结构与算法中枚举、模拟及排序的方法
本篇内容主要讲解“C语言数据结构与算法中枚举、模拟及排序的方法”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C语言数据结构与算法中枚举、模拟及排序的方法”吧!
枚举
连号区间数
来源：第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组
小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1∼N 的某个排列中有多少个连号区间呢？
这里所说的连号区间的定义是：
如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。
输出格式
输出一个整数，表示不同连号区间的数目。
数据范围
1≤N≤10000,
1≤Pi≤N
输入样例1：
4
3 2 4 1
输出样例1：
7
输入样例2：
5
3 4 2 5 1
输出样例2：
9
样例解释
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]
先来看暴力做法
先两次for()循环，对给出的数排序，然后再对区间内的数做判断，如果连续的就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); // 这里要把数组的初始状态存在bac数组中，因为每次sort排序后，数组的顺序会发生改变。 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); // 还原数组a的初始状态 } cout << res << endl; return 0;}但是这道题暴力做法在蓝桥杯中只能得60分，然后我们再来想一下怎么优化？
这里设两层循环，一层i表示左端点，第二层j表示右端点。如果要保持连续性的话那么有一个思路：因为是连续的所以在所取的[l，r]范围中寻找最大值，最小值。然后相减，最后和r-l（区间长度）作比较即可。除此之外当l=r时也算作连续
即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 ++ ) // 枚举区间左端点 { int minv = INF, maxv = -INF; for (int j = i; j < n; j ++ ) // 枚举区间右端点 { minv = min(minv, a[j]); maxv = max(maxv, a[j]); if (maxv - minv == j - i) res ++ ; } } cout << res << endl; return 0;}递增三元组
来源：第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组
给定三个整数数组
A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k) 满足：
1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27
首先考虑暴力做法，三个数组嵌套枚举，O(n3)的时间复杂度，n≤105一定会超时，这里提供代码，想试一下的可以试试
//暴力做法枚举（会超时）#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]; //运算 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;}尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。
用暴力查找时间总的时间复杂度为O(n2)，还是会超时。
二分
既然是查找，那么可以考虑进行二分查找，查找前先通过排序预处理三个数组，排序时间复杂度O(nlog2n)O(nlog2n),枚举B的所有元素+查找A,C中的元素时间复杂度也是O(nlog2n)O(nlog2n)，总的时间复杂度降为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]小的最后一个数 { 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;//所有数都大于等于b[i]的时候，low_a=-1,这样最后(low_a+1)*(n-low_b)的时候为0 int low_b=0,right_b=n-1; while(low_b<right_b) //找比b[i]大的第一个数 { 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;//所有数都小于等于b[i]的时候，low_b=n,这样最后(low_a+1)*(n-low_b)的时候为0 //if(low_a!=0&&low_b!=n-1)//最开始的时候用这种方法判断，后来发现不行 //如果只有一个数字可以的时候，这种情况无法判断， // 例如： // 1 4 5 // 5 5 9 // 4 6 7（10） 当b[i]=9的时候，c[i]=7和10的时候无法判断 res+=(long long)(low_a+1)*(n-low_b); } cout<<res<<endl; return 0;}双指针
进一步对查找进行优化，对于排过序的数组A和B，寻找A中小于B[i]的元素的个数可以考虑双指针算法，因为每个指针最多移动n次，故查找的时间复杂度降到O(n)，查找C与查找A同理，只是找第一个大于B的位置。
只需要将上述二分程序中的
//二分for(int i = 1; i <= n; ++i) { int key = num[1][i]; //A中二分查找第一个小于key的数的下标 int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1; //C中二分查找第一个大于key的数的下标 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);}完整的双指针程序为：
#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满足的个数以及C满足的个数相乘 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;}前缀和
之前的双指针算法时间复杂度的瓶颈为：排序O(nlog2n)O(nlog2n)
考虑是否可以不排序在O(n)的时间内解决此问题呢？
既然要排序实现快速的查找A中小于B[i]的数的个数，可以将数组A中所有元素出现的次数存入一个哈希表中，因为数组中元素的范围只有n5n5, 可以开一个大的数组cnta 作为哈希表。
在枚举B中元素时，我们需要快速查找找小于B[i]的所有元素的总数，只需要在枚举之前先将求出表中各数的前缀和即可。
查找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); //获取数i在A中有cntc[i]个，并对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]++; //获取数i在C中有cntc[i]个，并对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;}
分别是暴力，前缀和，双指针，二分。
模拟
特别数的和
来源：第十届蓝桥杯省赛C++B组,第十届蓝桥杯省赛JAVAB组
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示满足条件的数的和。
数据范围
1≤n≤10000
输入样例：
40
输出样例：
574
常用小技巧：关于取出x的每位数字 和 将字符数字转为数字
取出x的每位数字
int t = x % 10;
x /= 10;
2.将字符数字转为数字
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的个位 x /= 10; // 删掉x的个位 if (t == 2 || t == 0 || t == 1 || t == 9) { res += i; break; } } } cout << res << endl; return 0;}错误票据
来源：第四届蓝桥杯省赛C++A/B组,第四届蓝桥杯省赛JAVAA/B组
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。
全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式
第一行包含整数 N，表示后面共有 N 行数据。
接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。
输出格式
要求程序输出1行，含两个整数 m,n，用空格分隔。
其中，m表示断号ID，n表示重号ID。
数据范围
1≤N≤100
输入样例：
2
5 6 8 11 9
10 12 9
输出样例：
7 9
思路
找出最大和最小的数，同时再用一个数组记录每个数字的个数，最后遍历一遍即可
#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;}排序
快速排序
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
快排思路
有数组 q, 左端点 l, 右端点r
确定划分边界 x
将 q 分为 <=x 和 >=x 的两个小数组
i 的含义: i 之前的元素都 ≤x, 即 q[l..i−1]q[l..i−1] ≤x
j 的含义: j 之后的元素都 ≥x, 即 q[j+1..r]q[j+1..r] ≥x
结论: while循环结束后, q[l..j] ≤x,q[j+1..r] ≥x
简单不严谨证明:
while 循环结束时, i≥j
若 i>j , 显然成立
若 i=ji=j
∵∵ 最后一轮循环中两个 do−whiledo−while 循环条件都不成立
∴ q[i]≥x,q[j]≤x
∴ q[i]=q[j]=x
∴ 结论成立
递归处理两个小数组
#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;}归并排序
归并的题和快排的题是一样的，这里就不写题目了。
归并思路
有数组 q, 左端点 l, 右端点 r
确定划分边界 mid
递归处理子问题 q[l..mid], q[mid+1..r]
合并子问题
主体合并
至少有一个小数组添加到 tmp 数组中
收尾
可能存在的剩下的一个小数组的尾部直接添加到 tmp 数组中
复制回来
tmp 数组覆盖原数组
#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;}到此，相信大家对“C语言数据结构与算法中枚举、模拟及排序的方法”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
