【C++】 —— 笔试刷题day_27
一、kotori和气球
题目解析
这道题，有n中气球，每一种气球有无数多个；现在我们需要将这些气球摆成一排，但是，如果相邻的气球是相同的就会发生爆炸（也就是说，相同的气球相邻的摆法是不合法的）；
现在我们要求将气球摆成一排m个一共有多少种摆法；最终结果可能数据过大，我们输出最终结果对于109取模的结果即可。
算法思路
这道题整体来说还是比较简单的：
我们摆放第一个气球时，我们可以随便选取一个气球，那也就有n中可能；
当我们摆放第二个以及后面的气球时，我们不能摆放与上一个气球相同的气球，那也就有n-1种可能。
所以，我们最终结果就等于：n * (n-1)^(m-1)。
代码实现
这里通过查看数据范围我们可以发现：在运算的时候数据就看超出范围，所以在运算的过程中就进行%109操作。
#include<iostream>usingnamespace std;intmain(){int n,m; cin>>n>>m;longlong ret = n;for(int i =1;i < m;i++){ ret *=(n-1); ret %=109;} cout << ret << endl;return0;}二、走迷宫
题目解析
对于这道题，题目给定一个n*m规模的二维字符数组，每一个位置是*或者.（其中*表示当前位置有障碍物，.表示当前位置没有障碍物）
再给定(x1, y1)，(x2, y2)两个位置，然后让我们求从(x1 , y1)到(x2 , y2)最少的移动次数；
我们每次可以向上、向下、向左或者向右移动一格
算法思路
这道题很明显就是一个搜索类的题目了，所以这里就直接说思路了：
广度优先遍历bfs：
从(x1 , y1)位置开始广度优先遍历，每次向四周移动一步，直到走到(x2 , y2)位置或者 走完所有能到达的位置。
这里我们需要记录一下某一个位置是否到达过，所以这里可以使用已发给同等规模的二维数组vis来记录某一个位置是否到达过；
而这里我们也要记录从(x1, y1)位置开始，走到某一个位置需要多少步（这里也可以不记录，使用返回值来判断走到(x2 , y2)位置需要的步数）；
所以这里我们就使用一个表vis来记录某一个位置是否走到过，和从(x1, y1)走到某一个位置需要最少多少步；所以当vis[i][j] == -1时，表示这个位置还没走过；vis[i][j] > 0时，表示从(x1 , y1)走到(i , j)位置最少的移动次数）。
代码实现
这里我们要注意：题目中给定的下标是从(1 , 1)开始的。
#include<iostream>#include<queue>usingnamespace std;constint N =1001;char arr[N][N];int vis[N][N];int n, m;int dx[]={-1,1,0,0};int dy[]={0,0,-1,1};int x1, x2, y1, y2;intbfs(){if(arr[x2][y2]=='*')return-1;//初始化visfor(int i =0; i <= n; i++){for(int j =0; j <= m; j++){ vis[i][j]=-1;}} queue<pair<int,int>> pq; pq.push({x1, y1}); vis[x1][y1]=0;while(!pq.empty()){int a = pq.front().first;int b = pq.front().second; pq.pop();for(int i =0; i <4; i++){//遍历上下左右四个位置int x = a + dx[i];int y = b + dy[i];//(x,y)不越界，且该位置没有障碍物，且该位置没有到达过if(x >0&& x <= n && y >0&& y <= m && arr[x][y]=='.'&& vis[x][y]==-1){//从(a,b) ---> (x,y) vis[x][y]= vis[a][b]+1;if(x == x2 && y == y2)return vis[x][y]; pq.push({x, y});}}}return vis[x2][y2];}intmain(){ cin >> n >> m; cin >> x1 >> y1 >> x2 >> y2;for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ cin >> arr[i][j];}} cout <<bfs()<< endl;return0;}三、主持人调度（二）
题目解析
主持人调度(二) ：现在有n个活动，第i个活动的开始时间start[i]，结束时间end[i]；在主持人调度(一)中，只是让我们判断一个主持人能否主持这些活动；
现在我们要判断最少需要多少个主持人才能举办这n个活动；
一个主持人在同一时间只能参加一个活动。
算法思路
初看这道题，可能感觉毫无头绪，根本不知道这道题要如何去求；
现在来慢慢分析一下：
对于这n个活动，我们要求最少需要多少个主持人才能举办这些活动；
我们试想一下：现在有一个活动，它要被一个主持人主持，是不是分为两种情况：当前有主持人空闲，我们让空闲的主持人去主持即可；当前已有的主持人都在主持活动，我们就要一个新的主持人去主持这个活动。
那我们就可以根据这两种情况去思考：
我们需要知道当前已有主持人是否空闲，还要知道当前有多少个主持人；
那对于乱序的数据，我们没办法判断一个主持人是否在主持活动，所以我们要先对数组排序；
这样我们按顺序去安排每一个活动就方便很多了。
我们再来想：我们判断一个主持人是否空闲，是新活动的start开始时间和就活动的结束时间去比较的；
所以我们要记录每一个主持人要主持活动的结束时间end（无需记录开始时间）；
这样我们有一个活动需要安排时，将这个活动的start开始时间和所有主持人要主持活动的结束时间比较即可；
那问题又来了，一个一个去比较吗？
当然不是，如果一个一个去比较那时间复杂度就是O(n)了；
我们想一下：
- 如果活动的开始时间
start，它大于当前已存在主持人主持活动的结束时间的最小值，那肯定是存在主持人是可以去主持这个活动的； - 如果活动的开始时间
start，它是小于当前已经存在主持人主持活动的结束时间的最小值，那当前肯定是没有主持人可以去主持这个活动，就要找一个新的主持人去主持这个活动。
所以现在，我们不仅要记录当前已有主持人的数量，而且还要记录当前主持人要主持活动结束时间的最小值。
我们可以使用priority_queue来存储（也就是堆结构）
使用priority_aueue小根堆heap来存储主持人主持活动的最晚结束时间（因为一个主持人要支持多个活动）；
遍历所有活动：
如果一个活动的开始时间大于等于heap中堆顶数据heap.top()，那就表明有主持人可以去主持这个活动，删除堆顶数据，然后将这个活动的结束时间放入堆中即可。
如果一个活动的开始时间小于heap中堆顶数据heap.top()，那就表明没有主持人可以去主持这个活动，就要新增一个主持人；将这个活动的结束时间放入堆中即可。
最后堆heap中的数据个数就表示我们需要多少个主持人。
代码实现
classSolution{public:intminmumNumberOfHost(int n, vector<vector<int>>& startEnd){sort(startEnd.begin(), startEnd.end()); priority_queue<int, vector<int>, greater<int>> heap; heap.push(startEnd[0][1]);for(int i =1; i < startEnd.size(); i++){if(startEnd[i][0]>= heap.top()){ heap.pop(); heap.push(startEnd[i][1]);}else{ heap.push(startEnd[i][1]);}}return heap.size();}};到这里，本篇文章的内容就结束了，感谢支持
