解题思路
- -100和+100是没有用的，只要知道左边的飞船轴和右边的飞船轴离y轴一样近即可。为简单起见，我们将左边的轴设为-1，右边的设为1。
- 某个点能摧毁的飞船一定是因为有两个飞船关于这个点对称。即若(-1,y1)和(1,y2)能互相摧毁，说明他们关于(0,(y1+y2)/2)对称。
- 所以我们只用求出左边的点y1与右边的点y2的和y1+y2。（(y1+y2)/2为对称点，为了消除小数，我们不除以2）
- 记录每个y1+y2的值能消除左边的点的位置，和右边的点的位置。
- 找到两个不同的y1+y2，将他们能消除的左右边的位置分别合并，用（左边的数量+右边的数量）更新ans即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//输入
int a[100];int b[100];
//mp存a[i]+b[j]放在set数组的第几个位置
map <int,int> mp;
//k表示set数组中有效数据的长度
int k = 0;
set<int> sl[20010],sr[20010],sll,srr;
set<int>::iterator it;
int main(){
ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
for(int i = 1;i <= n; ++i) cin >> a[i];
for(int i = 1;i <= m; ++i) cin >> b[i];
for(int i = 1;i <= n; ++i){
for(int j = 1;j <= m; ++j){
//如果a[i]+b[j]没出现过就给一个新的set
//否则，就将这两个元素插入旧的set
if(mp[a[i]+b[j]] == 0){
mp[a[i]+b[j]] = ++k;
sl[k].insert(i);
sr[k].insert(j);
} else{
sl[mp[a[i]+b[j]]].insert(i);
sr[mp[a[i]+b[j]]].insert(j);
}
}
}
int ans = 0;
//W78的特判
if(k == 1){
ans = sl[1].size()+sr[1].size();
cout << ans << endl;
return 0;
}
//将任意两个不同的set合并，两个set的大小之和即为这两个点能摧毁的飞行船的数量。
for(int i = 1;i <= k; ++i){
for(int j = i+1;j <= k; ++j){
sll = sl[i];srr = sr[i];
for(it = sl[j].begin();it != sl[j].end(); it++){
sll.insert(*it);
}
for(it = sr[j].begin();it != sr[j].end(); it++){
srr.insert(*it);
}
ans = max(ans, (int)(sll.size()+srr.size()));
}
}
cout << ans << endl;
return 0;
}