（一）双指针
1.日志统计
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志日志共有 N 行。
其中每一行的格式是：
ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞小明就认为这个帖子曾是”热帖”。
具体来说如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K个赞该帖就曾是”热帖”。
给定日志请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K
以下 N 行每行一条日志包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围
1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3
解题思路：排序+双指针
①对所有的赞按时间排序
②通过双指针ij维护长度不大于d的区间并记录该帖子中的获赞数
#include<iostream>
#include<algorithm>
#include<cstdio>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int n,d,k;
int cnt[N];
bool ts[N];
PII flags[N];
int main()
{
int i,j;
scanf("%d%d%d",&n,&d,&k);
for(i=0;i<n;i++)
scanf("%d%d",&flags[i].x,&flags[i].y);
sort(flags,flags+n);
for(i=0,j=0;i<n;i++)
{
int id=flags[i].y;
cnt[id]++;
while(flags[i].x-flags[j].x>=d)
{
cnt[flags[j].y]--;
j++;
}
if(cnt[id]>=k)
ts[id]=true;
}
for(i=0;i<=100000;i++)
{
if(ts[i])
printf("%d\n",i);
}
return 0;
}
（二）BFS
1.献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫研究员们为了鼓励阿尔吉侬尽快到达终点就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道如果阿尔吉侬足够聪明它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置字符 E 表示奶酪所在的位置字符 # 表示墙壁字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置但不能走出地图边界。
输入格式
第一行是一个正整数 T表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R 和 C表示地图是一个 R×C 的矩阵。
接下来的 R 行描述了地图的具体内容每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式
对于每一组数据输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪则输出“oop!”（只输出引号里面的内容不输出引号）。
每组数据的输出结果占一行。
数据范围
1<T≤10,
2≤R,C≤200
输入样例：
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.
输出样例：
5
1
oop!解题思路：要求最短的距离应该用BFS来进行求解我们需要map数组来存储地图同时定义一个pair数组来存储当前或者下一步的位置
在定义一个vis数组来记录走的步数及是否走过该条路每进行一次bfs都要对vis数组进行初始化。
代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=210;
int x[]={1,-1,0,0};
int y[]={0,0,1,-1};
int t,r,c;
char map[N][N];
int vis[N][N];
bool check(int X,int Y)
{
if(X<0||X>=r||Y<0||Y>=c)
return false;
if(map[X][Y]=='#')
return false;
if(vis[X][Y]!=0)
return false;
return true;
}
int bfs(int bx,int by)
{
queue<PII> q;
memset(vis,0,sizeof(vis));
vis[bx][by]=0;
PII m;
m.x=bx,m.y=by;
q.push(m);
while(q.size())
{
PII tem=q.front();
if(map[tem.x][tem.y]=='E')
return vis[tem.x][tem.y];
q.pop();
for(int i=0;i<4;i++)
{
int X=tem.x+x[i];
int Y=tem.y+y[i];
if(check(X,Y)==false)
continue;
vis[X][Y]=vis[tem.x][tem.y]+1;
PII tem2;
tem2.x=X,tem2.y=Y;
q.push(tem2);
}
}
return 0;
}
int main()
{
int i,j,bx,by;
cin>>t;
while(t--)
{
cin>>r>>c;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
bx=i;
by=j;
}
}
}
int k=bfs(bx,by);
if(k)
{
cout<<k<<endl;
}
else
cout<<"oop!"<<endl;
}
return 0;
}
2.红与黑
有一间长方形的房子地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中每行包括 W 个字符。每个字符表示一块瓷砖的颜色规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时表示输入结束。
输出格式
对每个数据集合分别输出一行显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1≤W,H≤20
输入样例：
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例：
45
