牛客泡泡堂题解
解法1：AC
由题意得知一定有一列会被炸死，那么我们枚举这是哪一列。紧接着我们需要快速得知在第列的时候哪一行能炸死最多的人?于是这个我们可以用线段树或者
来维护。这里我选取的
维护。维护在第
列时每一行能炸死的人数，然后丢进
里面，从set取最大的人数那么就知道答案了。需要注意的是我们需要在计算第
列时每一行能炸死的人数时先把当前在第x列的人数去掉来防止重复计算。每次当我们枚举每一列时，我们只需要把
列的人贡献从set去掉(因为炸弹炸不到了)，同时还需要把
列的人的贡献加入set，可以看出对于每一个元素都会被加入两次删除两次，所以时间复杂度
，空间复杂度
set做法：
const int N = 200001;
vector<int>xpos[N];//保存的是第x列的人的y的坐标
int x[N],y[N];//保存的是第x列的个数，第y行的贡献
set<pair<int,int>>s;
class Solution {
public:
int BoomKill(int n, int m, vector<Point>& Player) {
// write code here
for(auto i:Player) {
xpos[i.x].push_back(i.y);
x[i.x]++;
}
for(int i=1;i<=min(n,m);i++) {//预处理在1列时每一行y的贡献
int cnt=0;
for(auto j:xpos[i])
y[j]++;
}
for(int i=1;i<=n;i++) {//预处理在1列时每一行y的贡献
s.insert({y[i],i});
}
for(auto j:xpos[1]) {//把第一列上的人的贡献删除
s.erase(s.lower_bound({y[j],j}));
s.insert({--y[j],j});
}
int ans=(*--s.end()).first+x[1];//第一列上答案的最大值
for(auto j:xpos[1]) {//把第一列上的人的贡献加上
s.erase(s.lower_bound({y[j],j}));
s.insert({++y[j],j});
}
for(int i=2;i<=n;i++) {
if(i-m>=1) {//把i-m列的人的贡献删去
for(auto j:xpos[i-m]) {
s.erase(s.lower_bound({y[j],j}));
s.insert({--y[j],j});
}
}
if(i+m-1<=n) {//把i+m-1列的人的贡献加上
for(auto j:xpos[i+m-1]) {
s.erase(s.lower_bound({y[j],j}));
s.insert({++y[j],j});
}
}
for(auto j:xpos[i]) {//把第i列上的人的贡献删除
s.erase(s.lower_bound({y[j],j}));
s.insert({--y[j],j});
}
ans=max(ans,(*--s.end()).first+x[i]);//更新答案
for(auto j:xpos[i]) {//把第i列上的人的贡献加上
s.erase(s.lower_bound({y[j],j}));
s.insert({++y[j],j});
}
}
return ans;
}
};线段树解法
static const int maxn = 200052;
int tr[maxn<<2];
void updata(int nl, int nr ,int now, int pos, int val) {
if (nl == nr) {
tr[now] += val;
return;
}
int mid = (nl+nr) / 2;
if (pos <= mid) {
updata(nl, mid, now*2, pos, val);
} else {
updata(mid+1, nr, now*2+1, pos, val);
}
tr[now] = max(tr[now*2], tr[now*2+1]);
}
int query(int nl, int nr, int now, int l, int r) {
if (l <= nl && nr <= r) {
return tr[now];
}
int mid = (nl+nr) / 2, ret = 0;
if (mid >= l) {
ret = max(ret, query(nl, mid, now*2, l, r));
}
if (mid+1 <= r) {
ret = max(ret, query(mid+1, nr, now*2+1, l, r));
}
return ret;
}
vector<int> a[maxn];
int BoomKill(int n, int m, vector<Point>& Player) {
// write code here
int num[maxn] = {0};
for (int i=0; i<Player.size(); i++) {
a[Player[i].x].push_back(i);
num[Player[i].x]++;
}
int ans = 0, l = 1, r = 1, x = 0;
while (x<n) {
x++;
while (r<=n && r <= x+m-1) {
for (int i=0; i<a[r].size(); i++) {
updata(1, n, 1, Player[a[r][i]].y, 1);
}
r++;
}
while (l<=n && l < x-m+1) {
for (int i=0; i<a[l].size(); i++) {
updata(1, n, 1, Player[a[l][i]].y, -1);
}
l++;
}
for (int i=0; i<a[x].size(); i++) {
updata(1, n, 1, Player[a[x][i]].y, -1);
}
ans = max(ans, query(1, n, 1, 1, n) + num[x]);
for (int i=0; i<a[x].size(); i++) {
updata(1, n, 1, Player[a[x][i]].y, 1);
}
}
return ans;
}解法2：TLE
枚举(x,y)点的位置，直接取计算答案。时间复杂度O(n^3),空间复杂度O(n*n)。
/**
* struct Point {
* int x;
* int y;
* };
*/
const int N = 200001;
class Solution {
public:
/**
*
* @param n int整型 n
* @param m int整型 m
* @param Player Point类vector Player
* @return int整型
*/
int BoomKill(int n, int m, vector<Point>& Player) {
// write code here
assert(1<=n&&n<=200000);
assert(1<=m&&m<=200000);
vector<vector<int>>mp(n+1, vector<int>(n+1));
for(auto i:Player) {
assert(1<=i.x&&i.x<=n);
assert(1<=i.y&&i.y<=n);
mp[i.x][i.y]++;
}
int ans=0;
for(int x=1;x<=n;x++) {
for(int y=1;y<=n;y++) {
int cnt=0;
for(int i=1;i<=n;i++) cnt+=mp[x][i];
for(int i=max(1,x-m+1);i<=min(n,x+m-1);i++) cnt+=mp[i][y];
cnt-=mp[x][y];
ans=max(ans,cnt);
}
}
return ans;
}
};解法3：在解法1的基础上再做优化，不用set来维护，用一个链表来维护。链表上维护的是当前这列出现过的权值，并用链表从小到大存下来，可以把复杂度降到O(n)，由于每次修改只会+1/-1，所以修改起来很简单。时间复杂度O(n)，空间复杂度O(n)，个人认为稍有难写，没有特别必要去这样写，用set蛮好的，当然如果实在要求O(n)可以这样写。
import java.util.*;
import static java.lang.Math.max;
import static java.lang.Math.min;
/*
* public class Point {
* int x;
* int y;
* }
*/
public class Solution {
/**
*
* @param n int整型 n
* @param m int整型 m
* @param Player Point类一维数组 Player
* @return int整型
*/
int N = 200001;
public int BoomKill(int n, int m, Point[] Player) {
// write code here
List<Set<Integer>> numList = new ArrayList<>();
for (int i = 0; i < Player.length + 1; i++) {
numList.add(new HashSet<>());
}
Set<Integer> set = numList.get(0);
for (int i = 1; i <= n; i++) {
set.add(i);
}
//当前范围内每行影响数量
int[] numArray = new int[N];
//记录每行中的最大值和最大值对应的行
int max = 0, maxIndex = 0;
List<Integer>[] xpos = new List[N];
for (int i = 0; i < xpos.length; i++) {
xpos[i] = new ArrayList<>();
}
//每列数量
int[] columnNum = new int[N];
for (Point i : Player) {
xpos[i.x].add(i.y);
columnNum[i.x]++;
}
for (int i = 1; i <= min(n, m); i++) {
for (int j : xpos[i]) {
numList.get(numArray[j]).remove(j);
numArray[j]++;
if (numArray[j] > max) {
max = numArray[j];
maxIndex = j;
}
numList.get(numArray[j]).add(j);
}
}
for (int j : xpos[1]) {//把第一列上的人的贡献删除
numList.get(numArray[j]).remove(j);
numArray[j]--;
numList.get(numArray[j]).add(j);
}
if (numArray[maxIndex] != max) {//更新max及index
if (numList.get(max).size() != 0) {
maxIndex = numList.get(max).iterator().next();
} else {
max--;
}
}
int ans = columnNum[1] + max;
for (int j : xpos[1]) {//把第一列上的人的贡献加上
numList.get(numArray[j]).remove(j);
numArray[j]++;
if (numArray[j] > max) {
max = numArray[j];
maxIndex = j;
}
numList.get(numArray[j]).add(j);
}
for (int i = 2; i <= n; i++) {
if (i - m >= 1) {//把i-m列的人的贡献删去
for (int j : xpos[i - m]) {
numList.get(numArray[j]).remove(j);
numArray[j]--;
numList.get(numArray[j]).add(j);
}
}
if (numArray[maxIndex] != max) {//更新max及index
if (numList.get(max).size() != 0) {
maxIndex = numList.get(max).iterator().next();
} else {
max--;
}
}
if (i + m - 1 <= n) {//把i+m-1列的人的贡献加上
for (int j : xpos[i + m - 1]) {
numList.get(numArray[j]).remove(j);
numArray[j]++;
if (numArray[j] > max) {
max = numArray[j];
maxIndex = j;
}
numList.get(numArray[j]).add(j);
}
}
for (int j : xpos[i]) {//把第i列上的人的贡献删除
numList.get(numArray[j]).remove(j);
numArray[j]--;
numList.get(numArray[j]).add(j);
}
if (numArray[maxIndex] != max) {//更新max及index
if (numList.get(max).size() != 0) {
maxIndex = numList.get(max).iterator().next();
} else {
max--;
}
}
ans = max(ans, max + columnNum[i]);//更新答案
for (int j : xpos[i]) {//把第i列上的人的贡献加上
numList.get(numArray[j]).remove(j);
numArray[j]++;
if (numArray[j] > max) {
max = numArray[j];
maxIndex = j;
}
numList.get(numArray[j]).add(j);
}
}
return ans;
}
}
