题解 | #牛客泡泡堂#

暴力

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param Player Point类vector Player
     * @return int整型
     */
    //每个玩家写入地图的时候，在炸弹能炸到的位置+1
    int BoomKill(int n, int m, vector<Point>& Player) {
        vector<vector<int> > map(n+1,vector<int>(n+1,0));  //初始化n*n二维动态数组，作为地图初始化值为0
        int num=Player.size();//玩家个数
        for(int i=1;i<num;i++){
            for(int j=1;j<n;j++)//x方向全死
                map[Player[i].x][j]++;
            int miny=max(1,Player[i].x-m+1);
            int maxy=min(n+1,Player[i].x+m);
            for(int j=miny;j<maxy;j++)//y方向按攻击力死
                map[j][Player[i].y]++;
            map[Player[i].x][Player[i].y]--;//重复计数
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(ans<map[i][j])
                    ans=map[i][j];
            }
        }
        return ans;
        // write code here
    }
};

优化

class Solution {
public:
    //每个玩家写入地图的时候，在炸弹能炸到的位置+1
    int BoomKill(int n, int m, vector<Point>& Player) {
       // vector<vector<int> > map(n+1,vector<int>(n+1,0));  //初始化n*n二维动态数组，作为地图初始化值为0
        vector<int> mapx(n+1,0);
        vector<list<int>> mapy(n+1);
        int num=Player.size();//玩家个数
        //存map
        for(int i=1;i<num;i++){
            mapx[Player[i].x]++;
            mapy[Player[i].y].push_back(Player[i].x);
        }
        //算一列
        int ans=0;
        for(int i=1;i<n+1;i++){//遍历每列
            int ynum=mapy[i].size();
            if(ynum!=0){//有人
                vector<int> caly(n+1,0);
                for(int j=0;j<ynum;j++){
                    int miny=max(1,mapy[i].front()-m+1);
                    int maxy=min(n+1,mapy[i].front()+m);
                    for(int k=miny;k<maxy;k++)//y方向按攻击力死
                        caly[k]++;
                    caly[mapy[i].front()]--;//x已经加过 要减一
                    mapy[i].pop_front();//删除当前元素
                }
                for(int j=1;j<n+1;j++){
                    if(ans<caly[j]+mapx[j])
                        ans=caly[j]+mapx[j];
                }
            }
        }
        return ans;
        // write code here
    }
};

进一步应该二分

class Solution {
public:
    int findy(vector<int>& y,int j,int m,int n){
        int miny=max(1,j-m+1);
        int maxy=min(n+1,j+m);
        int num=lower_bound(y.begin(),y.end(),maxy)-lower_bound(y.begin(),y.end(),miny);
        if(binary_search(y.begin(),y.end(),j))
            num--;
        return num;
    }
    //每个玩家写入地图的时候，在炸弹能炸到的位置+1
    int BoomKill(int n, int m, vector<Point>& Player) {
        vector<int> mapx(n+1,0);
        vector<vector<int>> mapy(n+1);
        int num=Player.size();//玩家个数
        //存map
        for(int i=1;i<num;i++){
            mapx[Player[i].x]++;
            mapy[Player[i].y].push_back(Player[i].x);
        }
        int maxx=0,maxy=0;
        for(int i=1;i<n+1;i++){
            if(maxy<mapy[i].size())
                maxy=mapy[i].size();
            if(maxx<mapx[i])
                maxx=mapx[i];
        }
        //算一列
        int ans=0;
        int magicnumy=max(maxy/2,1);
        int magicnumx=max(maxx/2,1);
        for(int i=1;i<n+1;i++){//遍历每列
            int ynum=mapy[i].size();
            if(ynum>magicnumy){//有人
                sort(mapy[i].begin(),mapy[i].end());//排序
                //mapy[i].sort();
                for(int j=1;j<n+1;j++){
                    if(mapx[j]>magicnumx){
                        int caly = findy(mapy[i],j,m,n);
                        if(ans<caly+mapx[j])
                            ans=caly+mapx[j];
                    }
                }
            }
        }
        return ans;
        // write code here
    }
};

这个方法有缺陷 最后一个样例每个点都出现两次，还是应该按玩家进行遍历