牛客泡泡堂题解

解法1：AC
由题意得知一定有一列会被炸死，那么我们枚举这是哪一列。紧接着我们需要快速得知在第 $x$ 列的时候哪一行能炸死最多的人?于是这个我们可以用线段树或者 $set$ 来维护。这里我选取的 $set$ 维护。维护在第 $x$ 列时每一行能炸死的人数，然后丢进 $set$ 里面，从set取最大的人数那么就知道答案了。需要注意的是我们需要在计算第 $x$ 列时每一行能炸死的人数时先把当前在第x列的人数去掉来防止重复计算。每次当我们枚举每一列时，我们只需要把 $x-m$ 列的人贡献从set去掉(因为炸弹炸不到了)，同时还需要把 $i+m-1$ 列的人的贡献加入set，可以看出对于每一个元素都会被加入两次删除两次，所以时间复杂度 $O(nlogk)$ ，空间复杂度 $O(k+n)$
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)可以这样写。

牛客泡泡堂题解

全站热榜

创作者周榜