一、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;
//初始化vis
for (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();
}
};
到这里，本篇文章的内容就结束了，感谢支持