2.枚举算法
1.枚举算法介绍
枚举算法是一种基本的算法思想,它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来,并进行验证和比较找到满足问题条件的最优解或者所有解。
枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观,不需要复杂的数学推导,易于实现。但是,由于需要穷举所有可能的情况,对于问题规模较大的情况,枚举算法的时间复杂度可能会非常高,效率较低。
2.解空间的类型
解空间可以是一个范围内的所有数字(或二元组、字符串等数据),或者满足某个条件的所有数字。
当然也可以是解空间树,一般可分为子集树和排列树,针对解空间树,需要使用回溯法进行枚举(在后面讲到搜索的时候会讲到)。我们目前仅使用循环去暴力枚举解空间,具体的解空间类型需要根据题目来理解构造。
3.循环枚举解空间
1.首先确定解空间的维度,即问题中需要枚举的变量个数。
- 例如当题目要求的是满足条件的数字时,我们可以循环枚举某个范围内的数字。
- 如果要求的是满足条件的二元组,我们可以用双重循环分别枚举第一个和第二个变量,从而构造出一个二元组。
2.对于每个变量,确定其可能的取值范围。这些范围可以根据问题的性质和约束条件来确定。这一步往往是时间复杂度优化的关键。
3.在循环体内,针对每个可能解进行处理。可以进行问题的验证、计算、输出等操作。
4.例题讲解
4.1 找到最多的数
问题描述
在一个 n × m n×m n×m的矩阵中,有一个数字出现了超过一半的次数,请设计一个高效算法找到这个数字。
输入格式
输入第一行包含两个整数 n n n和 m m m,表示矩阵的大小( 1 ≤ n , m ≤ 1 0 3 1 ≤n, m ≤10^{3} 1≤n,m≤103)。
接下来n行,每行包含m个正整数,表示矩阵中的元素。
输出格式
输出一个整数,表示矩阵中出现次数超过一半的数字
样例输入
3 3
1 2 3
2 2 2
1 2 2
样例输出
2
思路
这里借助于map进行处理。简单讲解以下map,map<int, int>
第一位代表key,也就是索引。第二位代表value,也就是具体的值。所以,key是单独唯一存在的。当出现统计数字的出现的个数时,可以使用key标识当前的数字,value代表出现的次数。
代码
#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n * m ; i ++) {
int x;
scanf("%d", &x);
mp[x] ++;
}
for(const auto &[x, y]: mp) {
if(y > n * m / 2)
printf("%d\n", x);
}
return 0;
}
4.2 小蓝的漆房
问题描述
小蓝是一位有名的漆匠,他的朋友小桥有一个漆房,里面有—条长长的走廊,走廊两旁有许多相邻的房子,每间房子最初被涂上了一种颜色。
小桥来找小蓝,想让他把整个走廊都涂成同一个颜色。小蓝告诉小桥,他每天只能涂一段长度为k的区间。对于每个区间,他可以选择将其中的房子重新涂上任何一种颜色,或者保持原来的颜色不变。
小桥想知道小蓝至少要涂几天,才能让整个走廊变得美丽。
请帮助小桥解决这个问题。
输入格式
第一行包含一个整数 t ( 1 ≤ 100 ) t (1 ≤100) t(1≤100),表示测试用例的数量。
每个测试用例的第一行包含两个整数 n n n和 k ( 1 ≤ k ≤ n ≤ 1 0 4 ) k (1 ≤k ≤n ≤10^4) k(1≤k≤n≤104),第二行包含 n n n个整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 60 ) a_{1}, a_{2},…, a_{n} (1 ≤a_{i}≤60) a1,a2,…,an(1≤ai≤60),分别表示每个房子最初的颜色。
保证所有测试用例中 n n n的总和不超过 1 0 4 10^{4} 104。
输出格式
对于每个测试用例,输出一个整数,表示小蓝需要涂漆的最少天数。
样例输入
2
5 2
1 1 2 2 1
6 2
1 2 2 3 3 3
样例输出
1
2
思路
首先,我们可以枚举整个走廊需要被涂上的颜色。因为颜色的种类数最多只有 60 60 60,所以我们可以尝试枚举每—种颜色。
对于每种颜色,我们需要计算涂上它需要的最少天数。我们可以从左到右遍历每个房子,如果该房子的颜色不是当前正在涂的颜色,那么我们就从该房子开始,向右涂 k k k个房子,直到将该区间都涂上目标颜色。具体来说,我们用a数组记录题目中给定的涂漆情况,用另一个数组b来记录当前的涂漆情况,每次枚举涂漆区间时,都将b数组中对应的区间涂成目标颜色。
在涂漆过程中,我们需要记录涂漆的天数cnt,每当涂漆颜色发生变化时,我们就需要增加一天。最终,我们可以对所有颜色涂上所需的天数取最小值,该最小值即为答案。
综上所述,解题步骤如下:
1.枚举整个走廊需要被涂上的颜色;
2.对于每种颜色,计算涂上它需要的最少天数:从左到右遍历每个房子,如果该房子的颜色不是当前正在涂的颜色,那么就从该房子开始,向右涂k个房子,直到将区间涂上目标颜色,同时记录涂漆天数cnt,每当涂漆颜色发生变化时,增加一天;
3.将所有颜色涂上所需的天数取最小值,即为答案。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N] , b[N];
signed main()
{
int T = 1;
cin >> T;
while(T --){
int n , k , res = 0x3f3f3f3f;
cin >> n >> k;
for(int i = 1 ; i <= n ; i ++) cin >> a[i];
for(int i = 1 ; i <= 60 ; i ++){
int cnt = 0;
for(int j = 1 ; j <= n ; j ++) b[j] = a[j];
for(int j = 1 ; j <= n ; j ++){
if(b[j] != i){
for(int h = j ; h <= j + k - 1 ; h ++) b[h] = i;
j = j + k - 1;
cnt ++ ;
}
}
res = min(res , cnt);
}
cout << res << '\n';
}
return 0;
}
优化后的思路:
实际上我们不必开辟b数组,不用模拟出涂漆的整个过程,而是记录次数即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N]; // 记录题目中给定的涂漆情况
int main() {
int t;
scanf("%d", &t); // 接收案例的个数
while(t --) {
int n, k;
int res = 0x3f3f3f3f; // 算法竞赛中常作为哨兵值,比较大的值,比较出较小的值
scanf("%d %d", &n, &k);// n为涂漆的总长度,其值代表不同颜色的涂漆,k为一天涂漆的区间
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
// 枚举不同的颜色,1~60
for(int i = 1; i <= 60; i ++) {
int cnt = 0;// 记录次数
for(int j = 1; j <= n; j ++) {
if(a[j] != i) { // 如果当前颜色不同, j~j+k-1将被涂漆
j = j + k - 1;
cnt ++;
}
}
res = min(res, cnt);
}
printf("%d\n", res);
}
return 0;
}