C++基础算法之枚举

发布时间:2024年01月12日

星光不问赶路人

岁月不负有心人


🎥烟雨长虹,孤鹜齐飞的个人主页

🔥个人专栏

期待小伙伴们的支持与关注!!!


目录

枚举算法的简介?

枚举算法的运用

#特别数的和

题目描述#

输入描述#

输入输出样例#

?#找到最多的数

问题描述#

输入格式#

输出格式#

#特殊日期

问题描述#

#不高兴的津津

题目描述#

输入描述#

输出描述#

输入输出样例#

#小蓝的漆房

问题描述#

输入格式#

输出格式#

总结:

枚举本质:

解题思路:

注意事项

枚举算法的简介?


枚举算法的介绍>:

<1>枚举通过穷举所有可能的情况来解决问题,本质上就是一种搜索算法

枚举算法的基本思想>:

<1>将问题的所有解的可能都列举出来

<2>根据题目要求验证和比较找到满足问题条件的优解或者所有解

枚举算法的优缺点>:

<1>优点:简单直观,不需要复杂的数学推导,易于实现

<2>缺点:运算量过大,当问题的规模变大的时候,循环的阶数越大,执行速度越慢

枚举算法的运用场景>:

<1>枚举算法适用于问题规模较小、解空间可穷举的情况

枚举算法的运用

#特别数的和


题目描述#

小明对数位中含有2、0、1、9的数字很感兴趣(不包括前导0),在 1 到 40 中这样的数包括 1、2、9、10至32、39和40,共28 个,他们的和是574。
请问,在 1 到 n 中,所有这样的数的和是多少?


输入描述#

输入格式#
输入一行包含两个整数 n (1<=n<=10^4)


输出描述#
输出一行,包含一个整数,表示满足条件的数的和。


输入输出样例#

输入

40

输出

574

#include<bits/stdc++.h>
using namespace std;
bool PanDuan(int n)
{
  while(n)
  {
    int num = n%10;
    if(num == 2||num == 0||num == 1||num == 9)
    {
      return true;
      break;
    }
    n /= 10;
  }
  return false;
}
int main()
{
  int n,sum = 0;
  cin>>n;
  for(int i = 1;i<=n;i++)
  {
    if(PanDuan(i))
    {
      sum += i;
    }
  }
  cout<<sum<<"\n";
  return 0;
}

将 1 到 n 所有的可能都遍历(枚举)一遍,并通过函数来判断是否满足题目需要

?#找到最多的数


问题描述#

在一个 n x m 的矩阵中,有一个数字出现了超过一半的次数,请设计一个高效算法找到这个数字。


输入格式#

输入第一行包含两个整数n和m,表示矩阵的大小(1<=n,m<=10^3)。接下来n行,每行包含m个正整数,表示矩阵中的元素。


输出格式#

输出一个整数,表示矩阵中出现次数超过一半的数字。

样例输入#

3 3
1 2 3
2 2 2
1 2 2

样例输出#

2

库函数?map?- 统计元素出现的次数

map<type1,type2> maps

type1是记入的元素,type2是计入的次数


#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main()
{
  int n,m,x;
  cin>>n>>m;
  for(int i=1;i<=n*m;i++)
  {
    cin>>x;
    mp[x]++;
  }
  for(const auto &[x,y]:mp)
{
  if(y*2>n*m)
  {
    cout<<x<<endl;
  }
}
  return 0;
}

#特殊日期

问题描述#

对于一个日期,我们可以计算出年份的各个数位上的数字之和,也可以分别计算月和日的各位数字之和。请问从1900年1月1日至9999年12月31日总共有多少天,年份的数位数字之和等于月的数位数字之和加日的数位数字之和。
例如,2022年11月13日满足要求,因为2+0+2+2(1+1)+(1+3)。
请提交满足条件的日期的总数量。


#include<bits/stdc++.h>
using namespace std;
int PanDuan(int n)
{
  int sum = 0;
  while(n)
  {
    sum += n%10;
    n /= 10;
  }
  return sum;
}
int main()
{
  int count = 0;
  int i,j,year,month,days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  for(year = 1900;year<=9999;year++)
  {
     if((year%4 == 0)&&(year%100 != 0)||(year %400 == 0)) //判断闰年
    {
      days[2] = 29;
    }
    else days[2] = 28;
    for(i = 1;i<=12;i++)
    {
     for(j = 1;j<=days[i];j++)
     {
        if( PanDuan(year) ==  PanDuan(i)+ PanDuan(j))
      {
        count++;
      }
     }
    }
  }
  cout<<count<<endl;
  return 0;
}

#不高兴的津津

题目描述#


津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴,而且上得越久就会越不高兴。假设津津不会因为其它事不高兴,并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排,看看下周她会不会不高兴;如果会的话,哪天最不高兴。


输入描述#


输入七行数据,分别表示周一到周日的日程安排。每行包括两个小于10的非负整数,用空格隔开,分别表示津津在学校上课的时间和妈妈安排她上课的时间。


输出描述#


输出一个数字。如果不会不高兴则输出0,如果会则输出最不高兴的是周几(用 1,2,3,4,5,6,7 分别表示周一,周二,周三,周四,周五,周六,周日)。如果有两天或两天以上不高兴的程度相当,则输出时间最靠前的天。


输入输出样例#

输入#

5 3
6 2
7 2
5 3
5 4
0 4
0 6

输出#

3

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,max = 0,num = 0;
  for(int i = 1;i<=7;i++)
  {
    cin>>a>>b;
    if(a+b>max)
    {
      max = a+b;
      num = i;
    }
  }
  if(num)
  {
    cout<<num;
  }
  else
  {
  cout<<"0";
  }
  return 0;
}

#小蓝的漆房

问题描述#

小蓝是一位有名的漆匠,他的朋友小桥有一个漆房,里面有一条长长的走廊,走廊两旁有许多相邻的房子,每间房子最初被涂上了一种颜色。
小桥来找小蓝,想让他把整个走廊都涂成同一个颜色。小蓝告诉小桥,他每天只能涂一段长度为k的区间。对于每个区间,他可以选择将其中的房子重新涂上任何一种颜色,或者保持原来的颜色不变
小桥想知道小蓝至少要涂几天,才能让整个走廊变得美丽。
请帮助小桥解决这个问题。


输入格式#

第一行包含一个整数t(t<=100),表示测试用例的数量。
每个测试用例的第一行包含两个整数n和k(1<=k<=n<10^4),第二行包含n 个整数 a1,a2,···,an (1<=ai<=60),分别表示每个房子最初的颜色。

1
2


保证所有测试用例中n的总和不超过10^4。

输出格式#

对于每个测试用例,输出一个整数,表示小蓝需要涂漆的最少天数。

样例输入#

2
5 2
1 1 2 2 1
6 2
1 2 2 3 3 3

样例输出#

1
2

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t=0;
    cin >> t;
    while(t--){
        int m,k;
        cin >> m >> k;        
        vector<int> arr(m);    
        set<int> s;     
        for (int i = 0; i < m; i++) {
            cin >> arr[i];
            s.insert(arr[i]);    
        }
        int num = 10000;
        for (auto &x: s) {        //遍历元素
            int sum = 0;
            for (int i = 0; i < m; i++) {
                if (arr[i] == x)continue;        //如果涂到的颜色与此次涂的颜色一致,那么跳过
                sum += 1;                        //如果不一致就加一
                i += k - 1;         //由于是i++,因为一次是涂k区间这么大,所以还需要+k所以这里要-1
            }
            num = min(num, sum);                 //记录最小次数
        }
        cout << num << '\n';
    }
   return 0;
}

总结:

枚举本质:

列举出该问题所有可能的解,并在逐一列举的过程中,检验每个可能解是否是问题的真正解,若是,我们采纳这个解,否则抛弃它


解题思路:

1.循环(枚举问题的解)
2.条件判断(筛选问题的解)
3.输出解的形式(输出所有符合题目要求的解或输出解的个数)


注意事项:

<1>枚举时要注意数据范围,列出所有可能情况,不能重复,不能遗漏

<2>枚举时要尽量缩小数据范围,提高计算效率,或者进行优化

<3>根据题目要求注意判断,挑选符合条件的解输出

文章来源:https://blog.csdn.net/2301_79201049/article/details/135553754
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。