题解 | #星球大战#

1、用x[i],y[i]存储i号基地的横纵坐标。用ans[i]记录i号战舰摧毁基地的数量
2、遍历m个战舰，每个战舰有两种类型
3、第一类可以纵向摧毁直线x=b,即坐标为(b,?)的所有基地。用mx[b]=i记录(b,?)被i号战舰纵向摧毁
4、第二类可以横向摧毁直线y=b,即坐标为(?,b)的所有基地。用my[b]=i记录(?,b)被i号战舰横向摧毁
5、遍历每个基地i，一些基地即被某个战舰横向摧毁又被另外一个战舰纵向摧毁，有些基地只被摧毁一次
6、对于一个基地（x[i],y[i]），若my[y[i]]=0且mx[x[i]]!=0，则该基地只被纵向摧毁。mx[[x[i]]=k，则k号战舰摧毁基地数+1。即ans[k]++;
7、若my[y[i]]！=0且mx[x[i]]==0，则该基地只被横向摧毁。my[[y[i]]=k，则k号战舰摧毁基地数+1。ans[k]++ 8、若my[y[i]]==0且mx[x[i]]==0，则该基地即被横向摧毁又被纵向摧毁，只需计算最早的

#include<bits/stdc++.h>
using namespace std;
map<int,int>mx,my;//储存每个基地被哪个战舰摧毁,mx[key]=value
                  //mx的key表示被摧毁基地的横坐标，value表示战舰编号
                  //my的key表示被摧毁基地的纵坐标，value表示战舰编号
const int N=1e5+5;
int x[N],y[N];//x[i]表示第i号基地的横坐标,y[i]表示第i号基地的纵坐标
int ans[N];//储存i号战舰摧毁的基地数量
int main()
{
	int m,n;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	int a,b;
	for(int i=1;i<=m;i++)//i个战舰
	{
		cin>>a>>b;
		if(a==0)//纵向摧毁所有横坐标为b的基地
		{
			if(mx[b]==0) mx[b]=i;//坐标为(b,?)的被i号战舰纵向摧毁
		}
		else//横向摧毁所有纵坐标为b的基地
		{
			if(my[b]==0) my[b]=i;//坐标为(?,b)的被i号战舰横向摧毁
		}
	}
	for(int i=1;i<=n;i++)
	{
		int nx=mx[x[i]],ny=my[y[i]];//坐标为(x[i],?)的基地被nx号战舰纵向摧毁
                                    //坐标为(?,y[i])的基地被ny号战舰横向摧毁
                                    //nx,ny都表示战舰编号
		if(nx==0||ny==0)//只被横向摧毁的或者只被纵向摧毁
		{
			if(nx!=0) ans[nx]++;//只被纵向摧毁
			else if(ny!=0) ans[ny]++;//只被哼向摧毁
		}
		else//即被横向摧毁，右被纵向摧毁，只能计算最先攻击的
		{ 
			if(nx < ny)//先被纵向摧毁
				ans[nx]++; 
			else //先被横向摧毁
				ans[ny]++;
		}
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<endl;
}