2019牛客暑期多校训练营（第十场）F——Popping Balloons（思维）

链接：https://ac.nowcoder.com/acm/contest/890/F?&headNav=acm
来源：牛客网
 

时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

Recently, an interesting balloon-popping game can be commonly found near the streets. The rule of this game is quite simple: some balloons are tied to cells of a lattice, and you are allowed to throw some darts to prick the balloons. The more balloons you pierce, the more incredible prize you will get.

Probably because too many people have got bored with this childish game, a new variation of the game has appeared. In this variation, you should prick the balloons by shooting an air rifle instead of throwing darts. You can make six shots in total, three horizontally and three vertically. If you shoot horizontally (vertically, resp.), all balloons in the row (column, resp.) are popped. In order to increase the difficulty, there is one restriction imposed on your shots: the distances between any two adjacent horizontal shots and any two adjacent vertical shots must all equal to a given number $r$. The problem is, what is the maximum number of balloons you can pop by making three horizontal and three vertical shots, under the aforementioned restriction.

输入描述:

The first line of input is two integers n, r (1≤n,r≤105)(1 \leq n, r \leq 10^5)(1≤n,r≤105), the number of balloons and the distance between any two adjacent horizontal or vertical shots.

The remaining part of the input is n lines, specifying the positions of the balloons. Each of these lines contains two integers x, y (0≤x,y≤105)(0 \leq x, y \leq 10^5)(0≤x,y≤105), denoting a balloon positioned at (x, y). Note that multiple balloons may lie in the same position.

输出描述:

Output the answer as a single integer in one line.

示例1

输入

复制

7 1
0 0
1 1
2 2
3 3
4 4
5 5
7 8

输出

复制

6

示例2

输入

复制

5 2
0 10
2 3
5 7
9 6
2 3

输出

复制

4

题意：打六枪，每次横着3枪竖着三枪，保证两枪之间的间隔为r，问最多打了多少气球（一打一行或者一列）

题解：统计每一行，每一列能打多少，以及该坐标有多少球，然后统计一下一行中和一列中相邻为r的行和列的和，作为该行或列的值，然后暴力枚举行里面的前6个和列里面的前六个即可（因为行列只需要3枪，6个就够了）~~

上代码：

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5+100;
struct hh{
	int id,num;
}a[MAX],b[MAX];
map<int,map<int,int> > mp;
int hang[MAX],lie[MAX];
bool cmp(hh a,hh b){
	return a.num>b.num;
}
int main(){
	int n,r,x,y;
	scanf("%d%d",&n,&r);
	int maxx1=0,maxx2=0;//为了减少时间
	int minn1=1e6,minn2=1e6;//为了减少时间
	for (int i = 0; i < n;i++){
		scanf("%d%d",&x,&y);
		mp[x][y]++;
		lie[x]++;
		hang[y]++;
		maxx1=max(maxx1,x);
		minn1=min(minn1,x);
		maxx2=max(maxx2,y);
		minn2=min(minn2,y);
	}
	for (int i = minn1; i <= maxx1;i++){
		a[i].id=i;
		a[i].num=lie[i];
		if(i+r<=maxx1) a[i].num+=lie[i+r];
		if(i-r>=minn1) a[i].num+=lie[i-r];
	}
	sort(a+minn1,a+maxx1+1,cmp);
	for (int i = minn2; i <= maxx2;i++){
		b[i].id=i;
		b[i].num=hang[i];
		if(i+r<=maxx2) b[i].num+=hang[i+r];
		if(i-r>=minn2) b[i].num+=hang[i-r];
	}
	sort(b+minn2,b+maxx2+1,cmp);
	int maxx=0;
	for (int i=minn1; i <= minn1+5;i++){//暴力枚举
		for (int j = minn2; j <= minn2+5;j++){
			int xx=a[i].id;
			int yy=b[j].id;
			int tmp=a[i].num+b[j].num;
			tmp-=mp[xx][yy]+mp[xx][yy-r]+mp[xx][yy+r];
			tmp-=mp[xx+r][yy]+mp[xx+r][yy-r]+mp[xx+r][yy+r];
			tmp-=mp[xx-r][yy]+mp[xx-r][yy-r]+mp[xx-r][yy+r];
			maxx=max(maxx,tmp);
		}
	}
	printf("%d\n",maxx);
	return 0;
}