【C++】 —— 笔试刷题day_27

一、kotori和气球

题目解析

这道题，有n中气球，每一种气球有无数多个；现在我们需要将这些气球摆成一排，但是，如果相邻的气球是相同的就会发生爆炸（也就是说，相同的气球相邻的摆法是不合法的）；

现在我们要求将气球摆成一排m个一共有多少种摆法；最终结果可能数据过大，我们输出最终结果对于109取模的结果即可。

算法思路

这道题整体来说还是比较简单的：

我们摆放第一个气球时，我们可以随便选取一个气球，那也就有n中可能；

当我们摆放第二个以及后面的气球时，我们不能摆放与上一个气球相同的气球，那也就有n-1种可能。

所以，我们最终结果就等于：n * (n-1)^(m-1)。

代码实现

这里通过查看数据范围我们可以发现：在运算的时候数据就看超出范围，所以在运算的过程中就进行%109操作。

#include <iostream>
using namespace std;int main()
{int n,m;cin>>n>>m;long long ret = n;for(int i = 1;i < m;i++){ret *= (n-1);ret %= 109;}cout << ret << endl;return 0;
}

二、走迷宫

题目解析

对于这道题，题目给定一个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>
using namespace std;
const int 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;
int bfs() {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];
}
int main() {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;return 0;
}

三、主持人调度（二）

题目解析

主持人调度(二) ：现在有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中的数据个数就表示我们需要多少个主持人。

代码实现

class Solution {public:int minmumNumberOfHost(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();}
};

到这里，本篇文章的内容就结束了，感谢支持