题解：两条公路
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/problem/21670
链接：https://ac.nowcoder.com/acm/problem/21670来源：牛客网
题目描述
平面上有n个点,现在你需要建造两条路，一条是斜率为1,
另一条斜率为-1
你的任务是让这两条路经过尽可能多的点
求最多经过几个点
输入描述:
第一行输入一个整数n
第二行输入n个整数表示x坐标
第三行输入n个整数表示y坐标
数据保证没有重点
1 ≤ N ≤ 1000,0 ≤ x[i],y[i] ≤ 999
输出描述:
输出一个整数
示例1
输入
复制
4
1 4 4 5
3 0 2 3
输出
复制
4
斜率为1的且在同一斜线的点y-x的值一定相同，斜率-1同一线的点y+x相同，先计算y-x和y+x的值
循环枚举y-x和y+x的值，暴力搜索答案
#include <bits/stdc++.h>typedef long long ll;using namespace std;map<int,int>m1,m2;int n,x[1005],y[1005],maxn;int jisuan(int k1,int k2){int i,j,c=0;for(i=1; i<=n; i++){if(x[i]-y[i]==k1||x[i]+y[i]==k2)c++;}return c;}int main(){int i,j,k,l;cin>>n;for(i=1; i<=n; i++){cin>>x[i];}for(i=1; i<=n; i++){cin>>y[i];}for(i=1; i<=n; i++){m1[x[i]-y[i]]++;m2[x[i]+y[i]]++;}map<int,int>::iterator it1,it2;for(it1=m1.begin(); it1!=m1.end(); it1++){for(it2=m2.begin(); it2!=m2.end(); it2++){maxn=max(maxn,jisuan(it1->first,it2->first));}}cout<<maxn;return 0;}
