1238. 日志统计
https://www.acwing.com/problem/content/1240/
使用双指针算法维护一个动态区间
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;//使用pair 默认按第一个大小然后第二个大小排序
const int N=1e5+5;
PII a[N];
int n,d,k;
int cnt[N];
bool st[N];
int main(){
cin>>n>>d>>k;
for(int i=0;i<n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a,a+n);
for(int i=0,j=0;i<n;i++){
int id=a[i].y;
cnt[id]++;
while(a[i].x-a[j].x>=d){
cnt[a[j].y]--;
j++;
}
if(cnt[id]>=k) st[id]=true;
}
for(int i=0;i<=100000;i++){
if(st[i]) cout<<i<<endl;
}
return 0;
}
// freopen("testdata.in", "r", stdin);
1101. 献给阿尔吉侬的花束
https://www.acwing.com/problem/content/1103/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
#define x first
#define y second
using namespace std;
typedef long long LL;
int T;
int R,C;
const int INF=0x3f3f3f3f;
char a[250][205];
int dist[250][250];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
typedef pair<int,int>PII;
int bfs(int x,int y){
memset(dist,0x3f,sizeof dist);
dist[x][y]=0;
queue<PII> q;
q.push({x,y});
while(q.size()){
auto t=q.front();
q.pop();
int x=t.x,y=t.y;
if(a[x][y]==‘E‘){
return dist[x][y];
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(dist[nx][ny]==INF && nx>=1 && nx<=R && ny >=1 && ny<=C && a[nx][ny]!=‘#‘){
dist[nx][ny]=dist[x][y]+1;
q.push({nx,ny});
}
}
}
return -1;
}
int main(){
cin>>T;
while(T--){
cin>>R>>C;
int x,y;
for(int i=1;i<=R;i++){
for(int j=1;j<=C;j++){
cin>>a[i][j];
if(a[i][j]==‘S‘){
x=i;
y=j;
}
}
}
int temp=bfs(x,y);
if(temp==-1) puts("oop!");
else cout<<temp<<endl;
}
return 0;
}
// freopen("testdata.in", "r", stdin);