2019牛客暑假多校训练赛第十场F Popping Balloons（优先队列维护）

题目链接：https://ac.nowcoder.com/acm/contest/890/F

题意：给定n,r，在一个1e5*1e5的方格图中有n个方格里面有气球，现在让竖向打三枪横向打三枪，必须满足三枪打的位置是x,x+r,x+r+r，问最多能打破多少气球，一枪打一行或列。

数据范围：1<=n,r,x,y<=1e5

思路：开一个优先队列从大到小排，对于每个气球可以由y，y-r，y-r-r三个位置开始的第一枪打到，那么对于这三个位置开枪的贡献就可以+1，处理好y以后就可以从0到1e5枚举x坐标打竖着的三枪，对于每个位置枚举时要把x,x+r,x+r+r这三列上的气球在之前处理的y的位置上减去，然后从优先队列里找到最大的y值就好了，最后再把减去的还回去。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,t,r;
vector<int>G[N*3];
priority_queue<pair<int,int> >Q;
int f[N*3];
void ins(int y,int val){
if(y>=0){
f[y]+=val;
Q.push(make_pair(f[y],y));
}
}
int gettop(){
pair<int,int>u=Q.top();
while(u.first!=f[u.second]){
Q.pop();
u=Q.top();
}
return u.first;
}
int main(){
scanf("%d%d",&n,&r);
int x,y;
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
ins(y,1);
ins(y-r,1);
ins(y-r-r,1);
}
int ans=0;
for(int i=0;i<=100000;i++){
int len=G[i].size();
for(int j=0;j<len;j++)ins(G[i][j],-1),ins(G[i][j]-r,-1),ins(G[i][j]-r-r,-1);
len=G[i+r].size();
for(int j=0;j<len;j++)ins(G[i+r][j],-1),ins(G[i+r][j]-r,-1),ins(G[i+r][j]-r-r,-1);
len=G[i+r+r].size();
for(int j=0;j<len;j++)ins(G[i+r+r][j],-1),ins(G[i+r+r][j]-r,-1),ins(G[i+r+r][j]-r-r,-1);
ans=max(ans,int(G[i].size()+G[i+r].size()+G[i+r+r].size()+gettop()));
len=G[i].size();
for(int j=0;j<len;j++)ins(G[i][j],1),ins(G[i][j]-r,1),ins(G[i][j]-r-r,1);
len=G[i+r].size();
for(int j=0;j<len;j++)ins(G[i+r][j],1),ins(G[i+r][j]-r,1),ins(G[i+r][j]-r-r,1);
len=G[i+r+r].size();
for(int j=0;j<len;j++)ins(G[i+r+r][j],1),ins(G[i+r+r][j]-r,1),ins(G[i+r+r][j]-r-r,1);
}
printf("%dn",ans);
return 0;
}

最后

以上就是贤惠高山为你收集整理的2019牛客暑假多校训练赛第十场F Popping Balloons（优先队列维护）的全部内容，希望文章能够帮你解决2019牛客暑假多校训练赛第十场F Popping Balloons（优先队列维护）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。